1018. 可被 5 整除的二进制前缀
1018. 可被 5 整除的二进制前缀
题目
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]
, thenx0 = 1
,x1 = 2
, andx2 = 5
.
Return an array of booleansanswer
whereanswer[i]
istrue
ifxi
is 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 either0
or1
.
题目大意
给定一个二进制数组 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
解题思路
累积计算二进制数:
- 使用一个变量
num
表示当前的二进制数。 - 遍历数组
nums
,对于每个数字bit
,通过位运算将其追加到当前的二进制数中:num = (num << 1 | bit)
。
- 使用一个变量
取模优化:
由于我们只关心能否被 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
变得过大,同时仍能正确判断是否整除。
- 例如,当
如果当前的
num
对 5 取模结果为 0,表示当前形成的二进制数能被 5 整除,将true
加入结果数组res
;否则加入false
。遍历结束后,返回结果数组
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 | 找出可整除性得分最大的整数 | 数组 | 🟢 | 🀄️ 🔗 |