How do I approach the 'Find the Divisibility Array of a String' problem?

You can solve the problem by calculating the remainder of each prefix modulo 'm' to check divisibility efficiently without converting the entire prefix to an integer.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the string, since you only need to iterate through the string once to calculate the remainders.

What are some common mistakes in solving this problem?

A common mistake is converting the entire prefix to an integer instead of using the modulo operation, which can be inefficient for large inputs.

How does modular arithmetic help in this problem?

Modular arithmetic allows you to efficiently check if a prefix is divisible by 'm' without needing to handle large integer values, reducing time and space complexity.

What should I do if 'm' is much larger than the length of the string?

Even if 'm' is large, you can still use modular arithmetic to avoid working with large numbers, ensuring your solution scales with both 'm' and string length.

#2575

Medium

auto_awesome数组·数学

LeetCode 题解工作台

找出字符串的可整除数组

给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。 word 的可整除数组 div 是一个长度为 n 的整数数组，并满足：如果 word[0,...,i] 所表示的数值能被 m 整除， div[i] = 1 否则， div[i]…

数组数学字符串

题目描述

给你一个下标从 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 <= 10⁵
word.length == n
word 由数字 0 到 9 组成
1 <= m <= 10⁹

lightbulb

解题思路

方法一：遍历 + 取模

我们遍历字符串 word，用变量 $x$ 记录当前前缀与 $m$ 的取模结果，如果 $x$ 为 $0$ ，则当前位置的可整除数组值为 $1$ ，否则为 $0$ 。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 word 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for candidates who optimize the remainder calculation process and handle large strings efficiently.
question_mark
Check how candidates handle large inputs and edge cases, such as very large 'm' values.
question_mark
Evaluate if the candidate can avoid converting strings to integers repeatedly, using modular arithmetic instead.

warning

常见陷阱

外企场景

error
Converting entire prefixes to integers instead of using modular arithmetic.
error
Not handling large values of 'm' efficiently, leading to potential performance issues.
error
Overcomplicating the solution by checking divisibility with brute force instead of using the modulo operation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider different values for 'm', including large and small values, to test the scalability of the solution.
arrow_right_alt
Explore edge cases like an input string of length 1 or 'm' being much larger than any prefix.
arrow_right_alt
Try variations with strings containing only a single repeating digit.

help

常见问题

外企场景

继续练习

#2125 银行中的激光束数量 #2019 解出数学表达式的学生分数 #2573 找出对应 LCP 矩阵的字符串