cells

2575. Find the Divisibility Array of a String#

You are given a string $word$ of length $n$, starting from index 0, consisting of digits from $0$ to $9$. You are also given a positive integer $m$.

The divisibility array of $word$, denoted as $div$, is an integer array of length $n$ that satisfies:

• If the value represented by $word[0,...,i]$ is divisible by $m$, then $div[i] = 1$
• Otherwise, $div[i] = 0$

Return the divisibility array of $word$.

Example 1:

Input: word = "998244353", m = 3
Output: [1,1,0,0,0,1,1,0,0]
Explanation: Only 4 prefixes can be divided by 3: "9", "99", "998244", and "9982443".

Example 2:

Input: word = "1010", m = 10
Output: [0,1,0,1]
Explanation: Only 2 prefixes can be divided by 10: "10" and "1010".

Note:

• $1 <= n <= 10^5$
• $word.length == n$
• $word$ consists of digits from $0$ to $9$
• $1 <= m <= 10^9$

Solution#

class Solution {
public:
    vector<int> divisibilityArray(string word, int m) {
        vector<int> res;
        long long num = 0;
        for (const auto &c : word) {
            num = (num * 10 + (c - '0')) % m;
            res.push_back(num == 0);
        }
        return res;
    }
};