You are given a 0-indexed string word of length n consisting of digits, and a positive integer m.
The divisibility array div of word is an integer array of length n such that:
div[i] = 1 if the numeric value of word[0,...,i] is divisible by m, ordiv[i] = 0 otherwise.Return the divisibility array of word.
Example 1:
Input: word = "998244353", m = 3 Output: [1,1,0,0,0,1,1,0,0] Explanation: There are only 4 prefixes that are divisible by 3: "9", "99", "998244", and "9982443".
Example 2:
Input: word = "1010", m = 10 Output: [0,1,0,1] Explanation: There are only 2 prefixes that are divisible by 10: "10", and "1010".
Constraints:
1 <= n <= 105word.length == nword consists of digits from 0 to 91 <= m <= 109Problem Overview: You are given a numeric string word and an integer m. For each prefix of the string, determine whether the number formed by that prefix is divisible by m. The result is a binary array where 1 means the prefix is divisible and 0 means it is not.
Approach 1: Iterative Modulo Calculation (O(n) time, O(1) space)
Construct the number incrementally while iterating through the string. Instead of converting the entire prefix into a large integer, maintain the current remainder using modular arithmetic. For each character, update the remainder with remainder = (remainder * 10 + digit) % m. If the remainder becomes 0, the current prefix is divisible by m, so record 1; otherwise record 0. This avoids large integer overflow and processes each character exactly once.
This approach relies on properties from math and sequential processing of a string. Since only the current remainder is stored, space usage stays constant. This is the optimal solution and scales efficiently even when the string length is up to 10^5.
Approach 2: Prefix Construction with BigInteger (O(n^2) time, O(n) space)
Another method builds each prefix number explicitly using a big integer representation. At every step, append the new digit to the previous value using a BigInteger (in Java) and check divisibility using mod. This works because big integer libraries support arbitrary precision arithmetic.
The drawback is that the prefix value grows with every digit. Each arithmetic operation becomes more expensive as the number length increases, leading to roughly O(n^2) total time in practice. Memory usage also grows because the full prefix number must be stored. This approach is easier to reason about conceptually but inefficient for long inputs.
Recommended for interviews: The iterative modulo approach is the expected solution. It demonstrates understanding of modular arithmetic and efficient prefix processing. Interviewers want to see that you avoid constructing huge integers and instead track the remainder while iterating through the array-like structure of digits. Mentioning the BigInteger approach first can show baseline thinking, but implementing the modulo trick proves strong algorithmic intuition.
Iterative Modulo Calculation: In this approach, we iterate through the string and maintain a running computation of the numeric value of the prefix modulo m. By keeping track of this value, we can determine if the current prefix is divisible by m without fully computing its numeric value (which could be large). This method efficiently checks divisibility by taking advantage of the mathematical properties of the modulo operation.
This C implementation iterates over each character in the given word, updating the prefix's numeric value modulo m. It determines if each prefix is divisible by m by checking if the modulo result is zero. The results are stored in the result array.
Time Complexity: O(n) - we traverse the string once.
Space Complexity: O(n) - the result array takes additional space.
Prefix Sum with BigInteger: This approach is useful when handling very large numbers that standard integer types cannot accommodate. By using big integer libraries or constructs, we can compute the prefix sum directly by considering each prefix as a whole number and using higher precision arithmetic to handle larger values. In languages where native big integer support is available, we leverage this capability to simplify our implementation.
This Java solution applies BigInteger for operations to manage very large prefix values. Such robust arithmetic ensures accuracy over potential integer overflow.
Java
Time Complexity: O(n) per arithmetic operation (though potentially slower due to BigInteger)
Space Complexity: O(n)
We iterate over the string word, using a variable x to record the modulo result of the current prefix with m. If x is 0, then the divisible array value at the current position is 1, otherwise it is 0.
The time complexity is O(n), where n is the length of the string word. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Iterative Modulo Calculation | Time Complexity: O(n) - we traverse the string once. |
| Prefix Sum with BigInteger | Time Complexity: O(n) per arithmetic operation (though potentially slower due to BigInteger) |
| Traversal + Modulo | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Modulo Calculation | O(n) | O(1) | Best for large strings and interview settings; avoids large integer construction |
| Prefix with BigInteger | O(n^2) | O(n) | Useful when demonstrating the direct numeric interpretation of prefixes using arbitrary precision integers |
Leetcode Weekly contest 334 - Medium - Find the Divisibility Array of a String • Prakhar Agrawal • 803 views views
Watch 9 more video solutions →Practice Find the Divisibility Array of a String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor