Find the Divisibility Array of a String

Med

#2355Time: O(n^2). The loop runs `n` times. Inside the loop, creating a substring of length `i+1` takes O(i) time. Creating a `BigInteger` from a string of length `i+1` and performing the `mod` operation also takes time proportional to the length of the string, roughly O(i). Therefore, the total time is the sum of `i` from 0 to `n-1`, which is O(n^2). This will be too slow for `n = 10^5`.Space: O(n). We need O(n) space for the output array. In each iteration, we create a substring and a `BigInteger` object, the largest of which will have a size proportional to `n`. So, the auxiliary space is O(n).

Patterns

Math

Data structures

Array String

Prompt

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, or
div[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 <= 10⁵
word.length == n
word consists of digits from 0 to 9
1 <= m <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the problem statement. For each prefix of the input string word, it converts the prefix into a number and then checks if that number is divisible by m.

Algorithm

Initialize an integer array div of size n.
Iterate with an index i from 0 to n-1.
Extract the prefix substring prefix = word.substring(0, i + 1).
Create a BigInteger from the prefix: BigInteger num = new BigInteger(prefix).
Create a BigInteger for the divisor m: BigInteger bigM = BigInteger.valueOf(m).
Calculate the remainder: BigInteger remainder = num.mod(bigM).
If remainder.equals(BigInteger.ZERO), set div[i] = 1.
Otherwise, set div[i] = 0.
After the loop, return the div array.

Walkthrough

The main challenge is that the numeric value of a prefix can be very large, exceeding the capacity of standard data types like long. To handle arbitrarily large integers, we can use the java.math.BigInteger class. The algorithm iterates from i = 0 to n-1, where n is the length of the string. In each iteration i, it extracts the substring word[0...i]. This substring is then converted into a BigInteger object. The mod operation of BigInteger is used to find the remainder when this number is divided by m. If the remainder is zero, div[i] is set to 1; otherwise, it's set to 0. This process is repeated for all prefixes.

1import java.math.BigInteger;2 3class Solution {4    public int[] divisibilityArray(String word, int m) {5        int n = word.length();6        int[] div = new int[n];7        BigInteger bigM = BigInteger.valueOf(m);8 9        for (int i = 0; i < n; i++) {10            String prefix = word.substring(0, i + 1);11            BigInteger num = new BigInteger(prefix);12            if (num.mod(bigM).equals(BigInteger.ZERO)) {13                div[i] = 1;14            } else {15                div[i] = 0;16            }17        }18        return div;19    }20}

Complexity

Time

O(n^2). The loop runs `n` times. Inside the loop, creating a substring of length `i+1` takes O(i) time. Creating a `BigInteger` from a string of length `i+1` and performing the `mod` operation also takes time proportional to the length of the string, roughly O(i). Therefore, the total time is the sum of `i` from 0 to `n-1`, which is O(n^2). This will be too slow for `n = 10^5`.

Space

O(n). We need O(n) space for the output array. In each iteration, we create a substring and a `BigInteger` object, the largest of which will have a size proportional to `n`. So, the auxiliary space is O(n).

Trade-offs

Pros

Simple and direct implementation of the problem statement.
Correctly handles arbitrarily large numbers.

Cons

Inefficient time complexity (O(n^2)), leading to a "Time Limit Exceeded" error on large inputs.
Repeatedly recomputes the value of prefixes from scratch, which is redundant.

This is an optimized approach that avoids handling large numbers directly by using properties of modular arithmetic. It calculates the remainder of the current prefix number based on the remainder of the previous prefix number.

Algorithm

Initialize an integer array div of size n.
Initialize a long variable remainder to 0. We use long to prevent potential overflow when remainder is multiplied by 10 before the modulo operation.
Iterate through the word string with an index i from 0 to n-1.
Get the numeric value of the current character: digit = word.charAt(i) - '0'.
Update the remainder: remainder = (remainder * 10 + digit) % m.
If remainder == 0, set div[i] = 1.
Otherwise, set div[i] = 0.
After the loop, return the div array.

Walkthrough

Let num_i be the number formed by the prefix word[0...i]. We can express num_i in terms of num_{i-1}: num_i = num_{i-1} * 10 + digit_i, where digit_i is the numeric value of word.charAt(i). We are interested in num_i % m. Using modular arithmetic properties, we have: num_i % m = (num_{i-1} * 10 + digit_i) % m This can be further broken down: num_i % m = ((num_{i-1} % m) * 10 + digit_i) % m This gives us a recurrence relation. If we let rem_i = num_i % m, then rem_i = (rem_{i-1} * 10 + digit_i) % m. We can iterate through the string, maintaining a running remainder. We start with a remainder of 0. For each digit, we update the remainder using the formula above. If the updated remainder is 0, the current prefix number is divisible by m. This way, we only deal with numbers that are at most m-1 (the remainder), avoiding overflow and the need for BigInteger.

1class Solution {2    public int[] divisibilityArray(String word, int m) {3        int n = word.length();4        int[] div = new int[n];5        long remainder = 0;6 7        for (int i = 0; i < n; i++) {8            int digit = word.charAt(i) - '0';9            remainder = (remainder * 10 + digit) % m;10            if (remainder == 0) {11                div[i] = 1;12            } else {13                div[i] = 0;14            }15        }16        return div;17    }18}

Complexity

Time

O(n). We iterate through the string of length `n` exactly once. All operations inside the loop (character access, arithmetic) take constant time.

Space

O(n). The space is dominated by the output array `div`. The auxiliary space used is O(1) for the `remainder` variable. If the output array is not counted, the space complexity is O(1).

Trade-offs

Pros

Highly efficient with linear time complexity.
Avoids creating large number objects and expensive operations, making it very fast.
Constant auxiliary space (excluding the output array).

Cons

Requires understanding of modular arithmetic to come up with the solution.

Solutions

Solution

1class Solution {2public3  int[] divisibilityArray(String word, int m) {4    int n = word.length();5    int[] ans = new int[n];6    long x = 0;7    for (int i = 0; i < n; ++i) {8      x = (x * 10 + word.charAt(i) - '0') % m;9      if (x == 0) {10        ans[i] = 1;11      }12    }13    return ans;14  }15}

1class Solution {2public:3  vector<int> divisibilityArray(string word, int m) {4    vector<int> ans;5    long long x = 0;6    for (char &c : word) {7      x = (x * 10 + c - '0') % m;8      ans.push_back(x == 0 ? 1 : 0);9    }10    return ans;11  }12};

1class Solution:2    def divisibilityArray(self, word: str, m: int) -> List[int]: ans = [] x = 0 for c in word: x = (x * 10 + int(c)) % m ans . append(1 if x == 0 else 0) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem