⚡Flashcard Drill➔
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

  1. A bitwise AND is greater than zero exactly when all chosen numbers share at least one common set bit.
  2. Fix a bit position b: every number having bit b set can be taken together, and their AND retains bit b.
  3. Taking the entire group is optimal for that bit, so the candidate answer is the count of numbers with bit b set.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Bit Manipulation Problems