Problem Description

You are given an array of positive integers called candidates. Your task is to find the size of the largest possible combination of elements from this array such that their bitwise AND is greater than 0.

The bitwise AND operation takes multiple numbers and performs an AND operation on each bit position across all numbers. For a combination to have a bitwise AND greater than 0, at least one bit position must have a 1 in all selected numbers.

For example:

• If candidates = [1, 5, 3], the bitwise AND would be 1 & 5 & 3 = 1 (in binary: 001 & 101 & 011 = 001)
• If candidates = [7], the bitwise AND is simply 7

The key insight is that for the bitwise AND of a combination to be greater than 0, there must be at least one bit position where all numbers in that combination have a 1. The solution counts how many numbers have a 1 at each bit position and returns the maximum count across all bit positions.

The approach iterates through each bit position (from 0 to the bit length of the maximum number) and counts how many numbers have a 1 at that position using x >> i & 1. This gives us the maximum possible combination size where all numbers share at least one common bit set to 1.

Intuition

To understand why this solution works, let's think about what makes a bitwise AND result greater than 0. When we perform AND operation on multiple numbers, the result is 0 only when there's no bit position where all numbers have a 1. Conversely, for the AND to be greater than 0, there must exist at least one bit position where every number in our combination has a 1.

Consider this: if we want the largest combination with AND > 0, we need to find the bit position that has the most 1s across all candidates. Why? Because at any given bit position, we can only include numbers that have a 1 at that position in our combination. If a number has a 0 at that bit position, including it would make that bit 0 in the final AND result.

For example, if we're looking at bit position 2 and we have numbers [5, 6, 7, 4] (in binary: [101, 110, 111, 100]), only numbers 5, 6, and 7 have a 1 at position 2. So the maximum combination for this bit position is 3.

The brilliant insight is that we don't need to generate all possible combinations and check their AND results. Instead, we can independently check each bit position and count how many numbers could potentially be in a combination for that bit. The maximum count across all bit positions gives us our answer.

This works because having multiple 1s at different bit positions doesn't help us include more numbers - we're constrained by the bit position with the fewest 1s among our chosen numbers. So we optimize by finding the single bit position that allows us to include the most numbers.

Solution Approach

The implementation uses bit manipulation to efficiently solve this problem. Here's how the solution works step by step:

1. Find the maximum bit length: First, we need to determine how many bit positions to check. We use max(candidates).bit_length() to find the number of bits needed to represent the largest number in the array. This ensures we check all relevant bit positions.

2. Iterate through each bit position: We loop through each bit position from 0 to the maximum bit length. For each position i, we want to count how many numbers have a 1 at that position.

3. Count 1s at each bit position: For each bit position i, we use the expression x >> i & 1 for every number x in candidates:

   • x >> i shifts the number right by i positions, bringing the bit at position i to the least significant position
   • & 1 masks everything except the least significant bit, giving us either 0 or 1
   • sum(x >> i & 1 for x in candidates) counts the total number of 1s at position i across all candidates

4. Track the maximum count: We maintain ans to store the maximum count found so far. After checking each bit position, we update ans using max(ans, current_count).

5. Return the result: The final value of ans represents the size of the largest combination where all numbers share at least one common bit set to 1.

For example, if candidates = [16, 17, 71, 62, 12, 24, 14]:

• Bit position 0: numbers with 1 at this position: [17, 71] → count = 2
• Bit position 1: numbers with 1 at this position: [71, 62, 14] → count = 3
• Bit position 2: numbers with 1 at this position: [71, 62, 12, 14] → count = 4
• Bit position 3: numbers with 1 at this position: [24, 62, 12, 14] → count = 4
• Bit position 4: numbers with 1 at this position: [16, 17, 24] → count = 3

The maximum count is 4, which is our answer.

Example Walkthrough

Let's walk through a small example with candidates = [5, 3, 6] to illustrate the solution approach.

First, let's convert these numbers to binary:

• 5 = 101
• 3 = 011
• 6 = 110

Step 1: Find maximum bit length The maximum number is 6, which requires 3 bits to represent (110 in binary). So we'll check bit positions 0, 1, and 2.

Step 2: Check each bit position

Bit position 0 (rightmost bit):

• 5 (101): bit at position 0 = 1
• 3 (011): bit at position 0 = 1
• 6 (110): bit at position 0 = 0 Count of 1s = 2 (numbers 5 and 3)

Bit position 1 (middle bit):

• 5 (101): bit at position 1 = 0
• 3 (011): bit at position 1 = 1
• 6 (110): bit at position 1 = 1 Count of 1s = 2 (numbers 3 and 6)

Bit position 2 (leftmost bit):

• 5 (101): bit at position 2 = 1
• 3 (011): bit at position 2 = 0
• 6 (110): bit at position 2 = 1 Count of 1s = 2 (numbers 5 and 6)

Step 3: Find maximum count The maximum count across all bit positions is 2.

Verification:

• At bit position 0, we can combine {5, 3}: 5 & 3 = 101 & 011 = 001 = 1 (> 0) ✓
• At bit position 1, we can combine {3, 6}: 3 & 6 = 011 & 110 = 010 = 2 (> 0) ✓
• At bit position 2, we can combine {5, 6}: 5 & 6 = 101 & 110 = 100 = 4 (> 0) ✓

Each bit position allows us to select 2 numbers maximum, and their AND is always greater than 0 because they all share a 1 at that specific bit position. The answer is 2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log M)

The algorithm iterates through each bit position from 0 to max(candidates).bit_length() - 1. The number of bit positions is log M where M is the maximum value in the candidates array. For each bit position, it checks all n candidates to count how many have that bit set using sum(x >> i & 1 for x in candidates), which takes O(n) time. Therefore, the total time complexity is O(n × log M).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space. The variable ans stores the maximum count, and the loop variable i is used for iteration. The generator expression sum(x >> i & 1 for x in candidates) doesn't create any additional data structures - it processes elements one at a time. No additional arrays, lists, or data structures that scale with input size are created, resulting in constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly assuming we need to find an actual combination with maximum AND value

Many people misinterpret this problem as finding the combination that produces the maximum AND result, rather than finding the largest-sized combination where AND > 0.

Wrong approach:

# Trying to maximize the AND result instead of combination size
max_and = 0
for i in range(len(candidates)):
    for j in range(i+1, len(candidates)):
        max_and = max(max_and, candidates[i] & candidates[j])

Correct understanding: We want the maximum NUMBER of elements that can be combined with AND > 0, not the maximum AND value itself.

2. Using fixed bit width instead of dynamic calculation

Hardcoding a bit width (like 32 or 64) can be inefficient or incorrect for the given input range.

Inefficient approach:

# Always checking 32 bits even if numbers are small
for bit_position in range(32):  # Wasteful if max number is small
    count = sum((x >> bit_position) & 1 for x in candidates)

Better approach:

# Only check necessary bits based on actual data
num_bits = max(candidates).bit_length()
for bit_position in range(num_bits):
    count = sum((x >> bit_position) & 1 for x in candidates)

3. Trying to generate all possible combinations

Attempting to check all possible subsets leads to exponential time complexity O(2^n).

Time-limit-exceeding approach:

from itertools import combinations
max_size = 0
for r in range(1, len(candidates) + 1):
    for combo in combinations(candidates, r):
        and_result = combo[0]
        for num in combo[1:]:
            and_result &= num
        if and_result > 0:
            max_size = r

Efficient O(n * log(max_value)) solution: Count bits at each position as shown in the correct solution.

4. Forgetting edge cases with single elements

When the array has only one element, some implementations might fail.

Potential issue:

# May fail if candidates has only one element
if len(candidates) < 2:
    return 0  # Wrong! Single element AND with itself is the element value

Correct handling: The bit-counting approach naturally handles single elements correctly since a single positive integer always has AND > 0 with itself.