banner
cells

cells

为美好的世界献上 bug

Find the divisible arrays of a string

2575. Find the Divisibility Array of a String#

You are given a string wordword of length nn, starting from index 0, consisting of digits from 00 to 99. You are also given a positive integer mm.

The divisibility array of wordword, denoted as divdiv, is an integer array of length nn that satisfies:

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

Return the divisibility array of wordword.

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<=1051 <= n <= 10^5
  • word.length==nword.length == n
  • wordword consists of digits from 00 to 99
  • 1<=m<=1091 <= 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;
    }
};
Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.