LeetCode 2275 - Largest Combination With Bitwise AND Greater Than Zero

The problem asks us to find the largest possible group of numbers from the candidates array such that the bitwise AND of every number in that group is greater than 0. A bitwise AND operation only keeps bits that are set to 1 in every participating number.

leetcodemediumarrayhash-tablebit-manipulationcounting

LeetCode Problem 2275

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Bit Manipulation, Counting

Solution

Problem Understanding

The problem asks us to find the largest possible group of numbers from the candidates array such that the bitwise AND of every number in that group is greater than 0.

A bitwise AND operation only keeps bits that are set to 1 in every participating number. For example:

6  = 110
14 = 1110
10 = 1010
--------------
AND = 0010 = 2

The result is greater than zero because at least one bit position remains set after combining all numbers.

This observation is the core of the problem. For a combination of numbers to have an AND greater than 0, there must exist at least one bit position where every number in that combination has a 1.

The input is an array of positive integers called candidates. We may choose any subset of these numbers, as long as the subset is non empty. Among all such subsets whose AND result is positive, we must return the maximum possible subset size.

The constraints are important:

  • 1 <= candidates.length <= 10^5
  • 1 <= candidates[i] <= 10^7

The array can contain up to one hundred thousand numbers, which immediately rules out any exponential subset enumeration approach. Additionally, the numbers are at most 10^7, which fits within 24 bits because:

2^24 = 16,777,216

This means we only need to examine a small fixed number of bit positions.

Several edge cases are important:

  • Arrays with only one element should return 1, since any positive number ANDed with itself remains positive.
  • Arrays where every number shares a common bit should return the full array size.
  • Arrays where no two numbers share any common set bit should return 1.
  • Duplicate values must be counted independently because combinations are based on indices, not unique values.

Approaches

Brute Force Approach

A brute force solution would generate every possible subset of the array, compute the bitwise AND for that subset, and track the largest subset whose AND is greater than zero.

This approach is correct because it explicitly checks all possible combinations. However, the number of subsets of an array with n elements is:

2^n

With n = 100000, this becomes completely infeasible.

Even for much smaller values, repeatedly computing AND values for all subsets would be prohibitively expensive.

Key Insight

The key observation is that a bitwise AND is greater than zero if and only if there exists at least one bit position that is set in every number of the combination.

Suppose we focus on a single bit position, such as bit k.

If a number has bit k set, then it can participate in a valid combination whose AND keeps bit k.

Therefore, the largest valid combination for bit k is simply the count of numbers having that bit set.

We can repeat this for every bit position and take the maximum count.

Since each number is at most 10^7, we only need to check about 24 bits. This transforms the problem from exponential complexity into a simple counting problem.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n × n) O(1) Enumerates every subset and computes AND
Optimal O(n × 24) O(1) Counts how many numbers contain each bit

Algorithm Walkthrough

  1. Initialize a variable max_size to store the largest valid combination found so far.
  2. Iterate through every possible bit position from 0 to 23. We use 24 because 10^7 fits within 24 bits.
  3. For each bit position, initialize a counter called count.
  4. Traverse the entire candidates array.
  5. For each number, check whether the current bit is set using:
number & (1 << bit)

If the result is non zero, increment count. 6. After processing all numbers for the current bit, count represents how many numbers share that bit. 7. Since every one of those numbers contains the same set bit, their collective AND will keep that bit and therefore remain greater than zero. 8. Update max_size with the maximum of its current value and count. 9. After checking all bit positions, return max_size.

Why it works

A combination has bitwise AND greater than zero exactly when at least one bit position remains set after ANDing all numbers together. That can only happen if every number in the combination has that bit set.

Therefore, for each bit position, the largest valid combination is the set of all numbers containing that bit. Taking the maximum over all bit positions guarantees the optimal answer.

Python Solution

from typing import List

class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        max_size = 0

        for bit in range(24):
            count = 0

            for number in candidates:
                if number & (1 << bit):
                    count += 1

            max_size = max(max_size, count)

        return max_size

The implementation directly follows the counting strategy described earlier.

The outer loop iterates through all relevant bit positions. Since the largest possible value is 10^7, checking 24 bits is sufficient.

Inside the inner loop, we test whether the current bit exists in each number using a bit mask. The expression:

number & (1 << bit)

creates a mask with only one bit set and checks whether that bit is present in number.

If the bit is set, we increment the counter because this number can participate in a combination that preserves this bit after AND operations.

After processing all numbers for a particular bit, we update the global maximum.

Because the number of bits is fixed and small, the algorithm runs efficiently even for the largest allowed input size.

Go Solution

func largestCombination(candidates []int) int {
    maxSize := 0

    for bit := 0; bit < 24; bit++ {
        count := 0

        for _, number := range candidates {
            if number&(1<<bit) != 0 {
                count++
            }
        }

        if count > maxSize {
            maxSize = count
        }
    }

    return maxSize
}

The Go implementation mirrors the Python logic very closely.

Go uses explicit integer operations and does not require type hints. The range based loop is used to iterate through the slice efficiently.

There are no overflow concerns because all values fit comfortably inside Go's standard integer range.

The solution uses constant extra space and performs only simple bit operations.

Worked Examples

Example 1

Input:

candidates = [16,17,71,62,12,24,14]

Binary representations:

Number Binary
16 10000
17 10001
71 1000111
62 111110
12 01100
24 11000
14 01110

We count how many numbers contain each bit.

Bit Position Numbers With Bit Set Count
0 17, 71 2
1 71, 62, 14 3
2 71, 62, 12, 14 4
3 62, 12, 24, 14 4
4 16, 17, 62, 24 4
5 71, 62 2
6 71 1

The maximum count is 4, so the answer is:

4

One valid combination is:

[16,17,62,24]

Their AND is:

16 & 17 & 62 & 24 = 16

which is greater than zero.

Example 2

Input:

candidates = [8,8]

Binary representation:

8 = 1000

Bit counts:

Bit Position Count
3 2

Both numbers share bit 3, so the AND remains positive.

Answer:

2

Complexity Analysis

Measure Complexity Explanation
Time O(n × 24) We scan all numbers for each of 24 bits
Space O(1) Only a few counters are used

The number of bits is fixed because the maximum value is bounded by 10^7. Therefore, the bit loop behaves like a constant factor, making the algorithm effectively linear in the size of the input array.

Test Cases

from typing import List

class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        max_size = 0

        for bit in range(24):
            count = 0

            for number in candidates:
                if number & (1 << bit):
                    count += 1

            max_size = max(max_size, count)

        return max_size

solution = Solution()

assert solution.largestCombination([16,17,71,62,12,24,14]) == 4  # Provided example
assert solution.largestCombination([8,8]) == 2  # Duplicate identical numbers
assert solution.largestCombination([1]) == 1  # Single element
assert solution.largestCombination([1,2,4,8]) == 1  # No shared bits
assert solution.largestCombination([7,7,7]) == 3  # All numbers share all bits
assert solution.largestCombination([5,10,15]) == 2  # Partial overlap
assert solution.largestCombination([1024,1024,1024,1]) == 3  # Large shared bit
assert solution.largestCombination([3,6,12,24]) == 2  # Different overlapping bits
assert solution.largestCombination([31,31,31,31,31]) == 5  # Entire array valid
assert solution.largestCombination([1,3,5,7,9]) == 4  # Shared least significant bit
Test Why
[16,17,71,62,12,24,14] Validates the main example
[8,8] Confirms duplicates are counted
[1] Tests smallest possible input
[1,2,4,8] Verifies disjoint bits case
[7,7,7] Ensures full array can be valid
[5,10,15] Tests partial bit overlap
[1024,1024,1024,1] Validates handling of higher bits
[3,6,12,24] Confirms multiple bit groups
[31,31,31,31,31] Tests maximum valid combination
[1,3,5,7,9] Checks repeated shared least significant bit

Edge Cases

One important edge case occurs when the array contains only a single number. Since every number in the input is guaranteed to be positive, the AND of a one element combination is always greater than zero. The implementation naturally handles this because at least one bit in the number will be counted once.

Another important case is when no two numbers share any set bit. For example:

[1,2,4,8]

Each number has a unique bit pattern, so no combination larger than size 1 can maintain a positive AND result. The algorithm correctly returns 1 because every bit count equals exactly one.

A third edge case involves duplicate numbers. For example:

[8,8,8,8]

All numbers share the same set bit, so the largest valid combination includes every element. Since the algorithm counts occurrences rather than distinct values, duplicates are handled correctly.

A final subtle edge case involves large bit positions near the upper constraint limit. Numbers close to 10^7 may use higher bits beyond the usual small examples. The implementation safely checks all 24 relevant bit positions, ensuring no valid combinations are missed.