Find the Divisibility Array of a String — Problem & Solution
Find the Divisibility Array of a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find the Divisibility Array of a String is a medium coding problem on arrays, strings and math, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Math
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string word of n digits and a positive integer m.
The divisibility array div of word has length n: div[i] = 1 if the number written by the prefix word[0..i] is divisible by m, and div[i] = 0 otherwise.
Return the divisibility array. The prefixes can be far too long to fit in any integer type.
Example 1
Input: word = "1020", m = 10
Output: [0,1,0,1]
Explanation: The prefixes are 1, 10, 102 and 1020; only 10 and 1020 are multiples of 10.
Example 2
Input: word = "2026", m = 4
Output: [0,1,0,0]
Example 3
Input: word = "777", m = 7
Output: [1,1,1]
Constraints
1 <= n <= 10^5word.length == nword consists of digits from 0 to 91 <= m <= 10^9
Hints for Find the Divisibility Array of a String
Hint 1
You never need a prefix's full value — only its remainder modulo
m.Hint 2
If the prefix ending at
i - 1leaves remainderr, the next prefix is10 × previous + digit.Hint 3
So
r = (r × 10 + digit) mod m. Withmup to 10^9,r × 10needs 64-bit arithmetic.
How to solve Find the Divisibility Array of a String
Carry the remainder of the current prefix modulo m; appending a digit multiplies the prefix by 10 and adds the digit, and remainders follow the same rule.
Approach
- Start with
r = 0. - For each digit
dofword, setr = (r × 10 + d) mod musing a 64-bit integer. - Append
1to the answer ifr == 0, otherwise0.
Why it works
If P = q·m + r is the previous prefix, the new prefix is 10P + d = 10q·m + (10r + d), which has the same remainder as 10r + d. By induction r is always the true remainder of the current prefix, and the prefix is divisible exactly when that remainder is 0.
Complexity
- Time —
O(n) - Space —
O(1) besides the output
Pitfalls
ris below 10^9, sor × 10 + 9can reach about 10^10 — overflowing 32-bit integers.- Do not parse the prefix as a number; it can be 100,000 digits long.
- A prefix of zeros is divisible by every
m(its value is 0).
Reference solution
Python
from typing import List
def divisibilityArray(word: str, m: int) -> List[int]:
r = 0
out = []
for ch in word:
r = (r * 10 + ord(ch) - 48) % m
out.append(1 if r == 0 else 0)
return outJava
public static int[] divisibilityArray(String word, int m) {
int n = word.length();
int[] out = new int[n];
long r = 0;
for (int i = 0; i < n; i++) {
r = (r * 10 + (word.charAt(i) - '0')) % m;
out[i] = r == 0 ? 1 : 0;
}
return out;
}C++
vector<int> divisibilityArray(string word, int m) {
vector<int> out(word.size());
long long r = 0;
for (size_t i = 0; i < word.size(); i++) {
r = (r * 10 + (word[i] - '0')) % m;
out[i] = r == 0 ? 1 : 0;
}
return out;
}JavaScript
var divisibilityArray = function(word, m) {
var r = 0, out = new Array(word.length);
for (var i = 0; i < word.length; i++) {
r = (r * 10 + (word.charCodeAt(i) - 48)) % m;
out[i] = r === 0 ? 1 : 0;
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.