Largest Combination With Bitwise AND Greater Than Zero
Problem
Return the size of the largest subset whose AND is > 0. Equivalent to: the largest count of numbers that share a common set bit.
candidates = [16, 17, 71, 62, 12, 24, 14]4def largest_combination(candidates):
best = 0
for b in range(32):
cnt = sum(1 for x in candidates if x >> b & 1)
best = max(best, cnt)
return bestfunction largestCombination(candidates) {
let best = 0;
for (let b = 0; b < 32; b++) {
let cnt = 0;
for (const x of candidates) if ((x >> b) & 1) cnt++;
if (cnt > best) best = cnt;
}
return best;
}class Solution {
public int largestCombination(int[] candidates) {
int best = 0;
for (int b = 0; b < 32; b++) {
int cnt = 0;
for (int x : candidates) if (((x >> b) & 1) != 0) cnt++;
best = Math.max(best, cnt);
}
return best;
}
}int largestCombination(vector<int>& candidates) {
int best = 0;
for (int b = 0; b < 32; b++) {
int cnt = 0;
for (int x : candidates) if ((x >> b) & 1) cnt++;
best = max(best, cnt);
}
return best;
}Explanation
We want the largest group of numbers whose bitwise AND is greater than zero. The key realization: an AND of several numbers is nonzero only if all of them share at least one common 1 bit. So the question becomes: which single bit position is set in the most numbers?
That turns a tricky subset search into simple counting. For each of the 32 bit positions b, we count how many candidates have that bit set using x >> b & 1, and track the largest such count in best.
This works because any set of numbers that all share bit b will have that bit surviving in their AND, keeping it positive. Conversely no larger group can exist, since a nonzero AND forces a shared bit, and we already checked every bit.
Example: candidates = [16, 17, 71, 62, 12, 24, 14]. Bit 4 (value 16) is set in 16, 17, 71, 24 — four numbers — and no other bit is shared by more, so the answer is 4.
We do a fixed 32 passes over the array, so the cost is simply proportional to the number of candidates.