What is the fastest way to find the largest combination with bitwise AND greater than zero?

Count the frequency of each bit in all numbers and return the maximum count. This ensures the subset has a shared bit and maximal size.

Can this problem be solved without bit manipulation?

Directly, no. Bit manipulation is essential to identify which numbers can contribute to a non-zero AND efficiently.

Why not check all subsets of the array?

Checking all subsets is exponential and infeasible for large arrays. Bit counting reduces complexity to O(n).

How does the hash lookup help in this problem?

It tracks the count of numbers with each bit set, allowing quick identification of the largest valid combination without full enumeration.

Does the pattern 'Array scanning plus hash lookup' apply here?

Yes, scanning the array and updating a hash or array of bit counts is exactly the pattern needed for this problem.

#2275

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

按位与结果大于零的最长组合

对数组 nums 执行按位与相当于对数组 nums 中的所有整数执行按位与。例如，对 nums = [1, 5, 3] 来说，按位与等于 1 & 5 & 3 = 1 。同样，对 nums = [7] 而言，按位与等于 7 。给你一个正整数数组 candidates 。计算 candid…

数组哈希表位运算计数

题目描述

对数组 nums 执行 按位与 相当于对数组 nums 中的所有整数执行 按位与 。

例如，对 nums = [1, 5, 3] 来说，按位与等于 1 & 5 & 3 = 1 。
同样，对 nums = [7] 而言，按位与等于 7 。

给你一个正整数数组 candidates 。计算 candidates 中的数字每种组合下 按位与 的结果。

返回按位与结果大于 0 的最长组合的长度。

示例 1：

输入：candidates = [16,17,71,62,12,24,14]
输出：4
解释：组合 [16,17,62,24] 的按位与结果是 16 & 17 & 62 & 24 = 16 > 0 。
组合长度是 4 。
可以证明不存在按位与结果大于 0 且长度大于 4 的组合。
注意，符合长度最大的组合可能不止一种。
例如，组合 [62,12,24,14] 的按位与结果是 62 & 12 & 24 & 14 = 8 > 0 。

示例 2：

输入：candidates = [8,8]
输出：2
解释：最长组合是 [8,8] ，按位与结果 8 & 8 = 8 > 0 。
组合长度是 2 ，所以返回 2 。

提示：

1 <= candidates.length <= 10⁵
1 <= candidates[i] <= 10⁷

lightbulb

解题思路

方法一：位运算

题目需要找到按位与结果大于 $0$ 的数字组合的最大长度，那么说明一定存在某个二进制位，所有数字在这个二进制位上都是 $1$ 。因此，我们可以枚举每个二进制位，统计所有数字在这个二进制位上的 $1$ 的个数，最后取最大值即可。

时间复杂度 $O(n \times \log M)$ ，其中 $n$ 和 $M$ 分别是数组 $\textit{candidates}$ 的长度和数组中的最大值。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        ans = 0
        for i in range(max(candidates).bit_length()):
            ans = max(ans, sum(x >> i & 1 for x in candidates))
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n * b) where b is the number of bits in the maximum integer, effectively O(n) since b is small and constant. Space complexity is O(1) because the bit count array uses fixed space independent of input size.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Look for an efficient solution avoiding full subset enumeration.
question_mark
Expect bitwise operations and counting techniques rather than brute force.
question_mark
They may hint at using a hash or counter for each bit position.

warning

常见陷阱

外企场景

error
Trying to compute bitwise AND for all possible subsets, which is exponential.
error
Ignoring that the AND must be greater than zero and including numbers without the required bit.
error
Miscounting bits or failing to handle large arrays efficiently.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the largest combination where bitwise OR meets a certain threshold.
arrow_right_alt
Count the number of combinations where a specific bit is set across all numbers.
arrow_right_alt
Determine the smallest combination where the bitwise AND is non-zero.

help

常见问题

外企场景

继续练习

#2206 将数组划分成相等数对 #2506 统计相似字符串对的数目 #1994 好子集的数目