Scan the array and count how many numbers have each bit set. The largest combination corresponds to the maximum count for any single bit, because a bitwise AND greater than zero requires that bit to be set in all numbers in the combination. Using a hash or counter allows fast aggregation and ensures O(n) time complexity for this pattern.
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.
How GhostInterview Helps
- Automatically identifies the key bit-counting pattern and avoids exhaustive subset checks.
- Provides step-by-step aggregation of bit frequencies to determine the correct combination size.
- Highlights common mistakes like including numbers without the critical bit and shows correct handling.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Largest Combination With Bitwise AND Greater Than Zero instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Largest Combination With Bitwise AND Greater Than Zero from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Determine if an array of 2n integers can be partitioned into n pairs where each pair contains identical elements using hash counting.
Open problem page#2506 Count Pairs Of Similar StringsCount similar string pairs by converting each word into a character-set signature and counting matching signatures efficiently.
Open problem page#1994 The Number of Good SubsetsFind the number of good subsets in an integer array, where each subset's product is the product of distinct primes.
Open problem page