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] <= 107This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), iterating each bit for each number.
Space Complexity: O(1).
| 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. |
Count Number of Maximum Bitwise-OR Subsets - Leetcode 2044 - Python • NeetCodeIO • 9,197 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