Description
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 <= 109
Solutions
Solution 1: Traversal + Modulo
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).
PythonJavaC++GoTypeScriptRustC
class Solution:
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(code-box)
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;
}
}(code-box)
class Solution {
public:
vector<int> divisibilityArray(string word, int m) {
vector<int> ans;
long long x = 0;
for (char& c : word) {
x = (x * 10 + c - '0') % m;
ans.push_back(x == 0 ? 1 : 0);
}
return ans;
}
};(code-box)
func divisibilityArray(word string, m int) (ans []int) {
x := 0
for _, c := range word {
x = (x*10 + int(c-'0')) % m
if x == 0 {
ans = append(ans, 1)
} else {
ans = append(ans, 0)
}
}
return ans
}(code-box)
function divisibilityArray(word: string, m: number): number[] {
const ans: number[] = [];
let x = 0;
for (const c of word) {
x = (x * 10 + Number(c)) % m;
ans.push(x === 0 ? 1 : 0);
}
return ans;
}(code-box)
impl Solution {
pub fn divisibility_array(word: String, m: i32) -> Vec<i32> {
let m = m as i64;
let mut x = 0i64;
word.as_bytes()
.iter()
.map(|&c| {
x = (x * 10 + i64::from(c - b'0')) % m;
if x == 0 {
1
} else {
0
}
})
.collect()
}
}(code-box)
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* divisibilityArray(char* word, int m, int* returnSize) {
int n = strlen(word);
int* ans = malloc(sizeof(int) * n);
long long x = 0;
for (int i = 0; i < n; i++) {
x = (x * 10 + word[i] - '0') % m;
ans[i] = x == 0 ? 1 : 0;
}
*returnSize = n;
return ans;
}(code-box)
