Find the Divisibility Array of a String
MedPrompt
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] = 1if the numeric value ofword[0,...,i]is divisible bym, ordiv[i] = 0otherwise.
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 == nwordconsists of digits from0to91 <= m <= 109
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
divof sizen. - Iterate with an index
ifrom0ton-1. - Extract the prefix substring
prefix = word.substring(0, i + 1). - Create a
BigIntegerfrom theprefix:BigInteger num = new BigInteger(prefix). - Create a
BigIntegerfor the divisorm:BigInteger bigM = BigInteger.valueOf(m). - Calculate the remainder:
BigInteger remainder = num.mod(bigM). - If
remainder.equals(BigInteger.ZERO), setdiv[i] = 1. - Otherwise, set
div[i] = 0. - After the loop, return the
divarray.
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.
import java.math.BigInteger; class Solution { public int[] divisibilityArray(String word, int m) { int n = word.length(); int[] div = new int[n]; BigInteger bigM = BigInteger.valueOf(m); for (int i = 0; i < n; i++) { String prefix = word.substring(0, i + 1); BigInteger num = new BigInteger(prefix); if (num.mod(bigM).equals(BigInteger.ZERO)) { div[i] = 1; } else { div[i] = 0; } } return div; }}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.
Solutions
Solution
class Solution {public int[] divisibilityArray(String word, int m) { int n = word.length(); int[] ans = new int[n]; long x = 0; for (int i = 0; i < n; ++i) { x = (x * 10 + word.charAt(i) - '0') % m; if (x == 0) { ans[i] = 1; } } 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.