#2275

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Largest Combination With Bitwise AND Greater Than Zero

Find the largest group of integers in an array whose bitwise AND is greater than zero using array scanning and hash lookup.

array hash table bit manipulation counting

Problem Statement

Given an array of positive integers candidates, determine the size of the largest subset where the bitwise AND of all its elements is greater than zero. Each element can be included only once, and subsets can have any number of elements from one up to the array length.

For every combination of elements in candidates, calculate their bitwise AND. Return the size of the largest combination where the result of this AND is strictly greater than zero. The input guarantees that the array has at least one element and each element is within reasonable positive bounds.

Examples

Example 1

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

Output: 4

The combination [16,17,62,24] has a bitwise AND of 16 & 17 & 62 & 24 = 16 > 0. The size of the combination is 4. It can be shown that no combination with a size greater than 4 has a bitwise AND greater than 0. Note that more than one combination may have the largest size. For example, the combination [62,12,24,14] has a bitwise AND of 62 & 12 & 24 & 14 = 8 > 0.

Example 2

Input: candidates = [8,8]

Output: 2

The largest combination [8,8] has a bitwise AND of 8 & 8 = 8 > 0. The size of the combination is 2, so we return 2.

Constraints

1 <= candidates.length <= 105
1 <= candidates[i] <= 107

Solution Approach

Count bits across all numbers

Iterate through each number in the array and count how many times each bit position is set. Use an array or hash map to store these counts. The maximum count for any bit indicates the size of the largest combination possible with a bitwise AND greater than zero.

Select the bit with maximum frequency

Identify the bit position with the highest count. This bit is guaranteed to be 1 in the largest subset that produces a bitwise AND greater than zero. All numbers having this bit set can form the largest valid combination.

Return the largest combination size

The size of the largest combination is equal to the count of numbers containing the selected bit. No larger subset can exist because any number without that bit would make the AND zero. This approach ensures optimal O(n) time and constant extra space for the bit counts.

Complexity Analysis

Metric	Value
Time	O(n \cdot b) = O(n)
Space	O(1)

Time complexity is O(n * b) where b is the number of bits in the maximum integer, effectively O(n) since b is small and constant. Space complexity is O(1) because the bit count array uses fixed space independent of input size.

What Interviewers Usually Probe

Look for an efficient solution avoiding full subset enumeration.
Expect bitwise operations and counting techniques rather than brute force.
They may hint at using a hash or counter for each bit position.

Common Pitfalls or Variants

Common pitfalls

Trying to compute bitwise AND for all possible subsets, which is exponential.
Ignoring that the AND must be greater than zero and including numbers without the required bit.
Miscounting bits or failing to handle large arrays efficiently.

Follow-up variants

Find the largest combination where bitwise OR meets a certain threshold.
Count the number of combinations where a specific bit is set across all numbers.
Determine the smallest combination where the bitwise AND is non-zero.

FAQ

What is the fastest way to find the largest combination with bitwise AND greater than zero?

Count the frequency of each bit in all numbers and return the maximum count. This ensures the subset has a shared bit and maximal size.

Can this problem be solved without bit manipulation?

Directly, no. Bit manipulation is essential to identify which numbers can contribute to a non-zero AND efficiently.

Why not check all subsets of the array?

Checking all subsets is exponential and infeasible for large arrays. Bit counting reduces complexity to O(n).

How does the hash lookup help in this problem?

It tracks the count of numbers with each bit set, allowing quick identification of the largest valid combination without full enumeration.

Does the pattern 'Array scanning plus hash lookup' apply here?

Yes, scanning the array and updating a hash or array of bit counts is exactly the pattern needed for this problem.

terminal

Solution

Solution 1: Bit Manipulation

The problem requires finding the maximum length of a combination of numbers where the bitwise AND result is greater than $0$. This implies that there must be a certain binary bit where all numbers have a $1$ at that position. Therefore, we can enumerate each binary bit and count the number of $1$s at that bit position for all numbers. Finally, we take the maximum count.

1

2

3

4

5

6

class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        ans = 0
        for i in range(max(candidates).bit_length()):
            ans = max(ans, sum(x >> i & 1 for x in candidates))
        return ans

Continue Practicing

#2206 divide array into equal pairs #2506 count pairs of similar strings #1994 the number of good subsets