NeetCode #866LC-2275MediumBit Manipulation
← Back to All Problems#866 · #2275 · Largest Combination With Bitwise AND Greater Than Zero(按位与大于零的最大组合)
📌 Problem Statement & Constraints
Given an integer array
candidates, choose a combination (subset) whose bitwise AND is greater than zero, and maximise its size. Return the size of the largest such combination. Constraints: 1 <= candidates.length <= 10^5, 1 <= candidates[i] <= 10^7.💡 Core Algorithmic Approaches
- A bitwise AND is greater than zero exactly when all chosen numbers share at least one common set bit.
- Fix a bit position
b: every number having bitbset can be taken together, and their AND retains bitb. - Taking the entire group is optimal for that bit, so the candidate answer is the count of numbers with bit
bset. - The overall answer is the maximum of these counts over all bit positions.
💻 Benchmark Python3 Implementation
class Solution:
def largestCombination(self, candidates: List[int]) -> int:
best = 0
for bit in range(25): # values are below 2^24
cnt = 0
for x in candidates:
if x >> bit & 1:
cnt += 1
best = max(best, cnt)
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(24 * n) = O(n): 24 fixed bit positions times a single pass each.
💾 Space Complexity
O(1): two counters.
⚠️ Interview Pitfalls & Follow-ups
- Trying to enumerate the subset: only the per-bit counts are needed, so enumeration is wasted work.
- Iterating too few bit positions: values up to 10^7 need 24 bits, so the range must reach bit 24.
- Thinking every chosen number must share all bits: a single common bit already makes the AND non-zero.
- Using pairwise
&over all pairs: that is O(n^2) and still does not yield the largest subset.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.