The bitwise AND of an array nums is the bitwise AND of all integers in nums.
nums = [1, 5, 3], the bitwise AND is equal to 1 & 5 & 3 = 1.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 <= 1051 <= candidates[i] <= 107Problem Overview: You are given an array of positive integers. The task is to choose the largest possible subset such that the bitwise AND of all chosen numbers is greater than zero. For the AND result to stay positive, every number in the subset must share at least one common bit set to 1.
Approach 1: Bit Counting (O(32 * n) time, O(1) space)
The key observation is that a positive AND result means at least one bit position remains set after combining all numbers. Instead of testing every subset, count how many numbers have each bit set. Iterate through every number and check each of the 32 bit positions using a bit mask like (num >> bit) & 1. Maintain a counter for each bit. The largest counter represents the maximum number of values that share that bit, meaning their AND will keep that bit as 1. The answer is simply the maximum frequency among all bit positions. This approach works because a subset with the same set bit guarantees the AND result remains non‑zero. The algorithm scans the array once and checks 32 bits per number, giving O(32 * n) time and constant memory.
This technique is a classic pattern when working with bit manipulation problems: instead of evaluating combinations directly, analyze bit positions independently and aggregate counts. It avoids exponential subset checks and converts the task into a simple counting pass.
Approach 2: Bit Manipulation with Early Exit (O(32 * n) time, O(1) space)
This variation follows the same bit counting idea but adds an optimization during iteration. For each bit position, scan the array and count how many numbers contain that bit. While scanning, track the remaining elements. If the current count plus the remaining possible elements cannot exceed the best answer found so far, you can stop processing that bit early. This pruning reduces unnecessary checks in cases where an early candidate already has a large frequency. The logic still relies on the same core observation: the maximum subset corresponds to the most frequent set bit.
Even with early termination, the theoretical complexity remains O(32 * n), but in practice it can skip work on dense inputs. The approach relies purely on integer bit checks and counters, making it memory efficient and easy to implement in languages like Python, Java, or C++.
Recommended for interviews: Interviewers expect the bit counting solution. A brute force subset check would be exponential and impractical. Recognizing that the AND result depends on shared bit positions demonstrates strong understanding of bit manipulation and counting techniques. Implementing the simple 32-bit frequency scan is both optimal and clean.
This approach focuses on determining how many numbers in the array have each particular bit set. The goal is to find the maximum count of numbers where at least one bit position has all of them contributing to a bitwise AND that results in a value greater than 0.
We iterate over each bit position (up to 32 if numbers can be up to 107) and count how many numbers have this bit set. The maximum of these counts is the size of the largest combination.
This C program defines a function largestCombination that takes an array of candidates and its size, then iterates over all 32 possible bit positions. For each bit position, it counts how many numbers in the array have that bit set, maintaining a maximum count found so far.
Time Complexity: O(n * 32) = O(n), where n is the number of candidates.
Space Complexity: O(1), no extra data structures are required beyond fixed-size variables.
This approach leverages the fact that the bitwise AND of a combination of numbers will be non-zero only if there exists at least one bit position that is set in all numbers of the combination. We attempt to identify this by checking which bit has the maximum number of numbers with it set and then determining if these numbers can form a valid combination.
This C solution checks for the highest count of numbers with a particular bit set, using steps similar to Approach 1, while considering each bit in isolation to determine maximum combination size potential.
Time Complexity: O(n), iterating each bit for each number.
Space Complexity: O(1).
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 1s at that bit position for all numbers. Finally, we take the maximum count.
The time complexity is O(n times log M), where n and M are the length of the array candidates and the maximum value in the array, respectively. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Bit Counting | Time Complexity: O(n * 32) = O(n), where n is the number of candidates. |
| Approach 2: Bit Manipulation with Early Exit | Time Complexity: O(n), iterating each bit for each number. |
| Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit Counting | O(32 * n) | O(1) | Best general solution. Simple implementation that counts how many numbers share each bit. |
| Bit Manipulation with Early Exit | O(32 * n) | O(1) | Useful when large counts appear early, allowing early termination during scans. |
Largest Combination With Bitwise AND Greater Than Zero | Detailed | Leetcode 2275 | codestorywithMIK • codestorywithMIK • 8,931 views views
Watch 9 more video solutions →Practice Largest Combination With Bitwise AND Greater Than Zero with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor