[LeetCode] 2575. Find the Divisibility Array of a String

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

找出字符串的可整除数组。

给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。

word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：

• 如果 word[0,…,i] 所表示的 数值 能被 m 整除，div[i] = 1
• 否则，div[i] = 0
  返回 word 的可整除数组。

思路

题意不难理解，就是从左往右扫描 word 里的数字前缀，看看这个前缀是否可以被 m 整除。注意题目给的数据范围，word 的长度最大可以到 10^5，如果一个数字的长度达到 10^5，不要说 long，哪怕是 double 也放不下。所以这道题的考点是需要在拼接每一个数字前缀的时候就要不断地对这个数字 % m，否则是会越界造成计算错误的。

复杂度

时间O(n)
空间O(n) - output

代码

Java实现

class Solution {
    public int[] divisibilityArray(String word, int m) {
        int n = word.length();
        int[] div = new int[n];
        long num = 0;
        for (int i = 0; i < n; i++) {
            num = num * 10 + (word.charAt(i) - '0');
            num %= m;
            if (num % m == 0) {
                div[i] = 1;
            }
        }
        return div;
    }
}