2575-找出字符串的可整除数组

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

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

• 如果 word[0,...,i] 所表示的 数值 能被 m 整除，div[i] = 1
• 否则，div[i] = 0

返回 __word 的可整除数组。

示例 1：

**输入：** word = "998244353", m = 3
**输出：** [1,1,0,0,0,1,1,0,0]
**解释：** 仅有 4 个前缀可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。

示例 2：

**输入：** word = "1010", m = 10
**输出：** [0,1,0,1]
**解释：** 仅有 2 个前缀可以被 10 整除："10" 和 "1010" 。

提示：

• 1 <= n <= 105
• word.length == n
• word 由数字 0 到 9 组成
• 1 <= m <= 109

前置知识：模运算的性质

设 a=k_1m+r_1,b=k_2m+r_2。

那么 (a+b)\bmod m = (r_1+r_2)\bmod m = (a\bmod m + b\bmod m)\bmod m。

思路

从左到右计算。设当前数字为 x，每遇到一个数字 d，就把 x 更新为 (10x+d)\bmod m。

附：视频讲解

[sol1-Python3]

class Solution:
    def divisibilityArray(self, word: str, m: int) -> List[int]:
        ans, x = [], 0
        for d in map(int, word):
            x = (x * 10 + d) % m
            ans.append(int(x == 0))
        return ans

[sol1-Go]

func divisibilityArray(word string, m int) []int {
	ans := make([]int, len(word))
	x := 0
	for i, c := range word {
		x = (x*10 + int(c-'0')) % m
		if x == 0 {
			ans[i] = 1
		}
	}
	return ans
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为 word 的长度。
• 空间复杂度：O(1)。返回值不计入。