可被 5 整除的二进制前缀

难度: Easy

给定一个二进制数组 nums ( 索引从0开始 )。

我们将x_i 定义为其二进制表示形式为子数组 nums[0..i] (从最高有效位到最低有效位)。

例如，如果 nums =[1,0,1] ，那么 x₀ = 1, x₁ = 2, 和 x₂ = 5。

返回布尔值列表 answer，只有当 x_i 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。

示例 1：

输入：nums = [0,1,1]
输出：[true,false,false]
解释：
输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为 true 。

示例 2：

输入：nums = [1,1,1]
输出：[false,false,false]

提示：

1 <= nums.length <= 10⁵
nums[i] 仅为 0 或 1

Submission

运行时间: 19 ms

内存: 17.5 MB

class Solution:
    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
        answer = list()
        prefix = 0
        for num in nums:
            prefix = ((prefix<<1) + num) % 5 
            answer.append(prefix == 0)
        return answer

Explain

这个题解使用了迭代的方法来计算每个前缀的二进制数对应的十进制数是否可以被5整除。在每次迭代中，它将之前的前缀数左移一位（相当于乘以2），然后加上当前的数字，得到新的前缀数。由于只关心这个数是否能被5整除，所以可以对每次得到的新前缀数取模5，这样可以防止数值过大。最后，判断当前的前缀数是否为0，如果为0则表示可以被5整除，将True添加到结果列表中，否则添加False。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
        answer = list()
        prefix = 0
        for num in nums:
            prefix = ((prefix << 1) + num) % 5  # 左移并加上当前数字，然后取模5
            answer.append(prefix == 0)  # 判断是否能被5整除
        return answer

Explore

在这个问题中，我们只关心二进制前缀转换成的十进制数是否能被5整除。计算完整的十进制数在大数组或长二进制序列情况下可能导致非常大的数值，这不仅会增加计算的复杂度，还可能导致整数溢出。通过仅保留模5的结果，我们可以显著降低数值的大小，同时保持能否被5整除的这一特性不变，因为一个数被5整除的性质仅依赖于它除以5的余数。

由于在每次迭代中，计算结果都取模5，因此prefix的值始终在0到4之间。这样的处理显著减少了数值的大小，避免了整数溢出的风险。Python中整数类型可以自动处理较大的数（自动转换为长整型），但在一些其他编程语言中，未经处理的大整数可能导致溢出。在这种情况下，取模操作是防止溢出的有效策略。

左移操作（<<）在二进制数中相当于将数值乘以2。例如，如果二进制数为`101`（十进制5），左移一位后变为`1010`（十进制10）。这个操作在构建二进制数的过程中非常关键，因为每遇到一个新的二进制位，之前的数值都需要左移（即乘以2），然后加上新的位（0或1）。这样可以从左到右逐步构建出完整的二进制数。取模5是在此基础上应用，以保持数值管理在一个较小的范围内。

在数学中，一个数如果能被另一个数整除，那么其除以那个数的余数必定为0。在题解中使用`prefix == 0`来判断是否能被5整除是基于这个数学原理的。因为prefix变量在每一步都执行了取模5的操作，所以prefix的值是当前二进制前缀对应的十进制数除以5的余数。当这个余数为0时，说明当前的二进制前缀可以被5整除，因此这种判断是准确的。