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 ofword[0,...,i]
is divisible bym
, 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 <= 105
word.length == n
word
consists of digits from0
to9
1 <= m <= 109
Solution: Big Integer Math
r = (r * 10 + word[i]) % m
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: vector<int> divisibilityArray(string word, int m) { vector<int> ans; long long r = 0; for (char c : word) { r = (r * 10 + c - '0') % m; ans.push_back(r == 0); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment