题目描述
给你一个 正整数 数组 nums
。
你需要检查是否可以从数组中选出 两个或更多 元素,满足这些元素的按位或运算(OR
)结果的二进制表示中 至少 存在一个尾随零。
例如,数字 5
的二进制表示是 "101"
,不存在尾随零,而数字 4
的二进制表示是 "100"
,存在两个尾随零。
如果可以选择两个或更多元素,其按位或运算结果存在尾随零,返回 true
;否则,返回 false
。
样例
输入:nums = [1,2,3,4,5]
输出:true
解释:如果选择元素 2 和 4,按位或运算结果是 6,二进制表示为 "110",存在一个尾随零。
输入: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)。
输入:nums = [1,3,5,7,9]
输出:false
解释:不存在按位或运算结果存在尾随零的选择方案。
限制
2 <= nums.length <= 100
1 <= nums[i] <= 100
算法
(思维题) $O(n)$
- 如果数组中出现两个或以上的偶数,则可以满足题目要求。
时间复杂度
- 遍历数组一次,时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
bool hasTrailingZeros(vector<int>& nums) {
bool seen = false;
for (int x : nums) {
if (x & 1)
continue;
if (seen)
return true;
seen = true;
}
return false;
}
};