1018. 可被 5 整除的二进制前缀

🟢   🔖  位运算 数组  🔗 力扣 LeetCode

题目

You are given a binary array nums (0-indexed).

We define xi as the number whose binary representation is the subarray nums[0..i] (from most-significant-bit to least-significant-bit).

• For example, if nums = [1,0,1], then x0 = 1, x1 = 2, and x2 = 5.

Return an array of booleansanswer whereanswer[i]istrue ifxiis divisible by5.

Example 1:

Input: nums = [0,1,1]

Output: [true,false,false]

Explanation: The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10.

Only the first number is divisible by 5, so answer[0] is true.

Example 2:

Input: nums = [1,1,1]

Output: [false,false,false]

Constraints:

• 1 <= nums.length <= 10^5
• nums[i] is either 0 or 1.

题目大意

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

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

• 例如，如果 nums =[1,0,1] ，那么 x0 = 1, x1 = 2, 和 x2 = 5。

返回布尔值列表 answer，只有当 xi 可以被 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^5
• nums[i] 仅为 0 或 1

解题思路

1. 累积计算二进制数：

   • 使用一个变量 num 表示当前的二进制数。
   • 遍历数组 nums，对于每个数字 bit，通过位运算将其追加到当前的二进制数中：num = (num << 1 | bit)。

2. 取模优化：

   由于我们只关心能否被 5 整除，可以在每次更新 num 后直接对 5 取模：num %= 5。

   • 例如，当 num = 6 时，对 5 取模结果为 6 % 5 = 1，在下一次循环中：
     • 如果直接用 num = 6：(6 << 1 | 1) % 5 = 3
     • 如果用对 5 取模后的 num = 6 % 5：((6 % 5) << 1 | 1) % 5 = 3
   • 这样可以避免 num 变得过大，同时仍能正确判断是否整除。

3. 如果当前的 num 对 5 取模结果为 0，表示当前形成的二进制数能被 5 整除，将 true 加入结果数组 res；否则加入 false。

4. 遍历结束后，返回结果数组 res。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度，遍历数组一次。
• 空间复杂度：O(n)，结果数组占用的空间。

代码

/**
 * @param {number[]} nums
 * @return {boolean[]}
 */
var prefixesDivBy5 = function (nums) {
	let num = 0,
		res = [];
	for (let bit of nums) {
		num = ((num << 1) | bit) % 5;
		res.push(num == 0);
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
2455	可被三整除的偶数的平均值		数组 数学	🟢	🀄️ 🔗
2644	找出可整除性得分最大的整数		数组	🟢	🀄️ 🔗