Skip to content

2575. Find the Divisibility Array of a String

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, 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 <= 105
  • word.length == n
  • word consists of digits from 0 to 9
  • 1 <= m <= 109

Solutions

Solution 1: Traversal + Modulo

Thinking

Mark whether each prefix integer is divisible by \(m\). Prefixes can be \(10^5\) digits, so the integers themselves cannot be built.

Remainders recur as \(x\leftarrow (10x+d)\bmod m\). A zero remainder writes \(1\), otherwise \(0\).

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)\).

1
2
3
4
5
6
7
8
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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
}

1
2
3
4
5
6
7
8
9
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
/**
 * 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;
}

Comments