2275. Largest Combination With Bitwise AND Greater Than Zero
Description
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 to1 & 5 & 3 = 1
. - Also, for
nums = [7]
, the bitwise AND is7
.
You are given an array of positive integers candidates
. Evaluate the bitwise AND of every combination of numbers of candidates
. Each number in candidates
may only be used once in each combination.
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 <= 105
1 <= candidates[i] <= 107
Solutions
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.
The time complexity is $O(n \times \log M)$, where $n$ and $M$ are the length of the array $\textit{candidates}$ and the maximum value in the array, respectively. The space complexity is $O(1)$.
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|