What does the bitwise OR operation do in this problem?

In this problem, the bitwise OR operation combines the bits of two or more numbers and the task is to check if the result has trailing zeros in its binary representation.

How do I check if the bitwise OR has trailing zeros?

To check if the bitwise OR of two numbers has trailing zeros, convert the result to binary and inspect the least significant bits. If the binary number ends in '0', it has trailing zeros.

Why is it important to only check pairs of elements?

Since a valid solution always exists with a pair of elements if one exists, limiting the problem to pairs optimizes the solution by reducing unnecessary checks.

Can I optimize the solution further?

The solution is already quite efficient by checking pairs early and terminating as soon as a valid pair is found. Further optimization would focus on specific cases or constraints.

What is the time complexity of this problem?

The time complexity is O(n^2) because we check all pairs of elements in the array, where n is the number of elements.

#2980

Easy

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

LeetCode 题解工作台

检查按位或是否存在尾随零

给你一个正整数数组 nums 。你需要检查是否可以从数组中选出两个或更多元素，满足这些元素的按位或运算（ OR ）结果的二进制表示中至少存在一个尾随零。例如，数字 5 的二进制表示是 "101" ，不存在尾随零，而数字 4 的二进制表示是 "100" ，存在两个尾随零。如果可以选择…

数组位运算

题目描述

给你一个 正整数 数组 nums 。

你需要检查是否可以从数组中选出 两个或更多 元素，满足这些元素的按位或运算（ OR）结果的二进制表示中至少存在一个尾随零。

例如，数字 5 的二进制表示是 "101"，不存在尾随零，而数字 4 的二进制表示是 "100"，存在两个尾随零。

如果可以选择两个或更多元素，其按位或运算结果存在尾随零，返回 true；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,4,5]
输出：true
解释：如果选择元素 2 和 4，按位或运算结果是 6，二进制表示为 "110" ，存在一个尾随零。

示例 2：

输入：nums = [2,4,8,16]
输出：true
解释：如果选择元素 2 和 4，按位或运算结果是 6，二进制表示为 "110"，存在一个尾随零。
其他按位或运算结果存在尾随零的可能选择方案包括：(2, 8), (2, 16), (4, 8), (4, 16), (8, 16), (2, 4, 8), (2, 4, 16), (2, 8, 16), (4, 8, 16), 以及 (2, 4, 8, 16) 。

示例 3：

输入：nums = [1,3,5,7,9]
输出：false
解释：不存在按位或运算结果存在尾随零的选择方案。

提示：

2 <= nums.length <= 100
1 <= nums[i] <= 100

lightbulb

解题思路

方法一：统计偶数个数

根据题意，我们可以知道，如果数组中存在两个或两个以上的元素，其按位或运算结果存在尾随零，那么数组中必然存在至少两个偶数。因此，我们可以统计数组中偶数的个数，如果偶数的个数大于等于 $2$ ，那么就返回 true，否则返回 false。

时间复杂度 $O(n)$ ，其中 $n$ 是数组的长度。空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def hasTrailingZeros(self, nums: List[int]) -> bool:
        return sum(x & 1 ^ 1 for x in nums) >= 2

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates an understanding of bitwise operations and binary representation.
question_mark
Candidate efficiently handles the problem by limiting the scope to pairs, avoiding unnecessary computations.
question_mark
Candidate shows knowledge of early termination techniques to optimize performance.

warning

常见陷阱

外企场景

error
Not reducing the problem to only pairwise checks, which may lead to inefficiency.
error
Overcomplicating the problem by trying to handle larger sets than necessary.
error
Failing to check the binary representation properly for trailing zeros in the OR result.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Check if the bitwise AND of selected numbers has trailing zeros.
arrow_right_alt
Check for a condition where the bitwise OR has multiple trailing zeros.
arrow_right_alt
Find if there's any subset whose bitwise OR contains a trailing zero.

help

常见问题

外企场景

继续练习

#2997 使数组异或和等于 K 的最少操作次数 #3011 判断一个数组是否可以变为有序 #3022 给定操作次数内使剩余元素的或值最小