跳至主要內容

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


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

🟢   🔖  位运算 数组  🔗 力扣open in new window LeetCodeopen in new window

题目

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] 仅为 01

解题思路

  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可被三整除的偶数的平均值数组 数学🟢🀄️open in new window 🔗open in new window
2644找出可整除性得分最大的整数数组🟢🀄️open in new window 🔗open in new window