Largest Combination With Bitwise AND Greater Than Zero

Med

#2073Time: O(N * K), where `N` is the number of candidates and `K` is the number of bits to check. Since `K` is a small constant (e.g., 24, based on the constraint `1 <= candidates[i] <= 10^7`), the complexity is effectively linear, `O(N)`.Space: O(1). We only use a few variables to store counts, regardless of the input size. An alternative implementation might use an array of size 24 or 32 to store bit counts, which is still constant space.1 company

Patterns

Bit Manipulation Counting

Data structures

Array Hash Table

Companies

Jump Trading

Prompt

The bitwise AND of an array nums is the bitwise AND of all integers in nums.

For example, for nums = [1, 5, 3], the bitwise AND is equal to 1 & 5 & 3 = 1.
Also, for nums = [7], the bitwise AND is 7.

You are given an array of positive integers candidates. Compute the bitwise AND for all possible combinations of elements in the candidates array.

Return the size of the largest combination of candidates with a bitwise AND greater than 0.

Example 1:

Input: candidates = [16,17,71,62,12,24,14]
Output: 4
Explanation: 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
Explanation: 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 <= 10⁵
1 <= candidates[i] <= 10⁷

Approaches

2 approaches with complexity analysis and trade-offs.

This approach leverages a key insight about the bitwise AND operation. For the AND of a set of numbers to be greater than zero, there must be at least one bit position that is '1' in every number of the set. The problem then transforms into finding the bit position that is set to '1' for the maximum number of candidates. This maximum count will be the size of the largest combination.

Algorithm

1. Initialize maxCount = 0.
1. Iterate through each bit position i from 0 to 23 (since 10^7 < 2^24).
1. For each bit i:
- a. Initialize currentCount = 0.
- b. Iterate through each number num in the candidates array.
- c. Check if the i-th bit is set in num using (num >> i) & 1 == 1.
- d. If the bit is set, increment currentCount.
1. After iterating through all numbers for a given bit, update maxCount = max(maxCount, currentCount).
1. After checking all bit positions, return maxCount.

Walkthrough

Instead of checking combinations of numbers, we can check combinations of bits. For the bitwise AND of a group of numbers to be greater than 0, there must be at least one bit position i that is set to 1 for all numbers in that group.

This means that any valid combination must consist entirely of numbers that share at least one common set bit. To find the largest such combination, we should find the bit position that is most frequently set across all numbers in the candidates array.

The algorithm is as follows: we iterate through each possible bit position (from 0 up to a limit determined by the maximum possible value of a candidate). For each bit position, we count how many numbers in the candidates array have that bit set. The maximum count we find across all bit positions is our answer. Since the maximum candidate value is 10^7, which is less than 2^24, we only need to check bits 0 through 23.

1class Solution {2    public int largestCombination(int[] candidates) {3        int maxCount = 0;4        // The maximum value is 10^7, which is less than 2^24.5        // So we only need to check bits from 0 to 23.6        // We can iterate up to 30 for safety with standard integer sizes.7        for (int i = 0; i < 24; i++) {8            int currentCount = 0;9            for (int num : candidates) {10                // Check if the i-th bit is set in num11                // (num >> i) shifts the i-th bit to the least significant position12                // & 1 isolates this bit.13                if (((num >> i) & 1) == 1) {14                    currentCount++;15                }16            }17            maxCount = Math.max(maxCount, currentCount);18        }19        return maxCount;20    }21}

This approach is highly efficient and easily passes the given constraints.

Complexity

Time

O(N * K), where `N` is the number of candidates and `K` is the number of bits to check. Since `K` is a small constant (e.g., 24, based on the constraint `1 <= candidates[i] <= 10^7`), the complexity is effectively linear, `O(N)`.

Space

O(1). We only use a few variables to store counts, regardless of the input size. An alternative implementation might use an array of size 24 or 32 to store bit counts, which is still constant space.

Trade-offs

Pros

Very efficient in both time and space.
Simple to implement once the core insight is understood.
Easily handles the given constraints.

Cons

Requires understanding the properties of the bitwise AND operation to arrive at the insight, making it less direct than the brute-force method.

This approach involves generating every possible non-empty combination (subsequence) of the candidates array. For each combination, we calculate the bitwise AND of its elements. If the result is greater than zero, we compare its size with the largest size found so far and update it if necessary.

Algorithm

1. Initialize a variable maxSize to 0.
1. Generate all 2^N - 1 non-empty subsequences of the input array, where N is the number of candidates. This can be done by iterating from 1 to 2^N - 1 and using the bitmask of the iterator to select elements.
1. For each generated subsequence:
- a. Initialize currentAnd with the first element of the subsequence.
- b. Iterate through the rest of the elements of the subsequence and perform a bitwise AND operation with currentAnd.
- c. After iterating through all elements, check if currentAnd > 0.
- d. If it is, update maxSize = max(maxSize, currentSubsequence.size()).
1. After checking all subsequences, maxSize holds the result.

Walkthrough

The most straightforward way to solve the problem is to simulate the process described. We can generate all possible combinations of numbers from the candidates array, calculate their bitwise AND, and if the result is positive, we note the size of that combination. We keep track of the maximum size found across all combinations.

Generating all combinations can be done in several ways, such as using recursion (backtracking) or iteratively using bit manipulation. For an array of size N, there are 2^N - 1 non-empty combinations. The iterative bitmask approach is shown below. Each integer i from 1 to 2^N - 1 represents a unique subsequence, where the j-th bit of i being set means the j-th element of candidates is included in the subsequence.

1class Solution {2    public int largestCombination(int[] candidates) {3        int n = candidates.length;4        int maxSize = 0;5 6        // Iterate through all 2^n - 1 non-empty subsets7        for (int i = 1; i < (1 << n); i++) {8            int currentAnd = -1; // A value with all bits set9            int currentSize = 0;10            boolean firstElement = true;11 12            // Build the current combination based on the bits of i13            for (int j = 0; j < n; j++) {14                // Check if the j-th element is in the current subset15                if ((i & (1 << j)) != 0) {16                    if (firstElement) {17                        currentAnd = candidates[j];18                        firstElement = false;19                    } else {20                        currentAnd &= candidates[j];21                    }22                    currentSize++;23                }24            }25 26            if (currentAnd > 0) {27                maxSize = Math.max(maxSize, currentSize);28            }29        }30        return maxSize;31    }32}

This approach is too slow for the given constraints but is a valid starting point for understanding the problem.

Complexity

Time

O(N * 2^N), where `N` is the number of candidates. There are `2^N` subsequences, and for each, we iterate up to `N` elements to calculate the AND. This is computationally infeasible for the given constraints.

Space

O(1). The iterative bitmask approach uses constant extra space.

Trade-offs

Pros

Conceptually simple and directly follows the problem definition.

Cons

Extremely inefficient and will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest input sizes (e.g., N > 20).

Solutions

Solution

1class Solution {2public3  int largestCombination(int[] candidates) {4    int ans = 0;5    for (int i = 0; i < 32; ++i) {6      int t = 0;7      for (int x : candidates) {8        t += (x >> i) & 1;9      }10      ans = Math.max(ans, t);11    }12    return ans;13  }14}

1class Solution {2public:3  int largestCombination(vector<int> &candidates) {4    int mx = *max_element(candidates.begin(), candidates.end());5    int m = 32 - __builtin_clz(mx);6    int ans = 0;7    for (int i = 0; i < m; ++i) {8      int cnt = 0;9      for (int x : candidates) {10        cnt += x >> i & 1;11      }12      ans = max(ans, cnt);13    }14    return ans;15  }16};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem