What is the best way to check binary prefixes for divisibility by 5?

Use a running modulo 5 computation where each prefix is updated as current = (current * 2 + nums[i]) % 5.

Can leading zeros affect the result?

No, leading zeros do not change the numeric value of the prefix; the modulo arithmetic handles them correctly.

Is converting the full binary prefix to decimal necessary?

No, direct conversion can cause overflow; using modulo updates efficiently avoids large numbers.

Does this problem use a specific algorithm pattern?

Yes, it combines Array iteration with Bit Manipulation, tracking prefixes via modulo arithmetic.

How large can nums be while staying efficient?

Arrays up to length 10^5 are handled efficiently with O(n) time and O(1) extra space using the modulo approach.

#1018

Easy

auto_awesome数组·结合·位运算·操作

LeetCode 题解工作台

可被 5 整除的二进制前缀

给定一个二进制数组 nums ( 索引从0开始 )。我们将 x i 定义为其二进制表示形式为子数组 nums[0..i] (从最高有效位到最低有效位)。例如，如果 nums =[1,0,1] ，那么 x 0 = 1 , x 1 = 2 , 和 x 2 = 5 。返回布尔值列表 answer ，…

数组位运算

题目描述

给定一个二进制数组 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

lightbulb

解题思路

方法一：模拟

我们用一个变量 $x$ 来表示当前的二进制前缀，然后遍历数组 $nums$ ，对于每个元素 $v$ ，我们将 $x$ 左移一位，然后加上 $v$ ，再对 $5$ 取模，判断是否等于 $0$ ，如果等于 $0$ ，则说明当前的二进制前缀可以被 $5$ 整除，我们将 $\textit{true}$ 加入答案数组，否则将 $\textit{false}$ 加入答案数组。

时间复杂度 $O(n)$ ，忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

class Solution:
    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
        ans = []
        x = 0
        for v in nums:
            x = (x << 1 | v) % 5
            ans.append(x == 0)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) as we iterate through the array once. Space complexity is O(n) for the answer array; extra space is O(1) since only the current modulo is tracked. Large arrays are handled efficiently due to modulo arithmetic and bit shift updates.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on the binary-to-decimal conversion via prefix computation.
question_mark
Look for constant space optimization using modulo rather than full number storage.
question_mark
Expect clarity in handling edge cases like leading zeros and small arrays.

warning

常见陷阱

外企场景

error
Attempting to convert each prefix to decimal directly, causing overflow.
error
Ignoring modulo arithmetic, resulting in incorrect divisibility checks.
error
Misinterpreting the binary order and updating prefixes incorrectly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Check divisibility by other numbers like 3 or 7 instead of 5 using the same prefix technique.
arrow_right_alt
Compute sums of binary prefixes rather than divisibility flags.
arrow_right_alt
Return indices of prefixes divisible by 5 instead of boolean array.

help

常见问题

外企场景

继续练习

#996 平方数组的数目 #995 K 连续位的最小翻转次数 #982 按位与为零的三元组