Problem

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.

Examples

Example 1

1
2
3

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

1
2
3

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^5
  • word.length == n
  • word consists of digits from 0 to 9
  • 1 <= m <= 10^9

Solution

Method 1 – Prefix Modulo Accumulation

Intuition

To check if the prefix of the string up to index i is divisible by m, we can maintain the current value modulo m as we iterate through the string. This avoids handling very large numbers.

Approach

  1. Initialize a variable to store the current prefix modulo m.
  2. Iterate through each character in the string:
    • Update the prefix modulo by multiplying the previous value by 10, adding the current digit, and taking modulo m.
    • If the current prefix modulo is 0, set div[i] = 1, else 0.
  3. Return the divisibility array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    vector<int> divisibilityArray(string word, int m) {
        int n = word.size();
        vector<int> ans(n);
        long long cur = 0;
        for (int i = 0; i < n; ++i) {
            cur = (cur * 10 + (word[i] - '0')) % m;
            ans[i] = (cur == 0 ? 1 : 0);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func divisibilityArray(word string, m int) []int {
    n := len(word)
    ans := make([]int, n)
    cur := 0
    for i := 0; i < n; i++ {
        cur = (cur*10 + int(word[i]-'0')) % m
        if cur == 0 {
            ans[i] = 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

class Solution {
    fun divisibilityArray(word: String, m: Int): IntArray {
        val n = word.length
        val ans = IntArray(n)
        var cur = 0L
        for (i in 0 until n) {
            cur = (cur * 10 + (word[i] - '0')) % m
            ans[i] = if (cur == 0L) 1 else 0
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def divisibilityArray(self, word: str, m: int) -> list[int]:
        n = len(word)
        ans = [0] * n
        cur = 0
        for i, ch in enumerate(word):
            cur = (cur * 10 + int(ch)) % m
            ans[i] = 1 if cur == 0 else 0
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn divisibility_array(word: String, m: i32) -> Vec<i32> {
        let n = word.len();
        let mut ans = vec![0; n];
        let mut cur = 0i64;
        for (i, ch) in word.chars().enumerate() {
            cur = (cur * 10 + (ch as i64 - '0' as i64)) % m as i64;
            ans[i] = if cur == 0 { 1 } else { 0 };
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    divisibilityArray(word: string, m: number): number[] {
        const n = word.length, ans = Array(n).fill(0);
        let cur = 0;
        for (let i = 0; i < n; ++i) {
            cur = (cur * 10 + Number(word[i])) % m;
            ans[i] = cur === 0 ? 1 : 0;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string, as we process each character once.
  • 🧺 Space complexity: O(n), for the output array.