#2275
Largest Combination With Bitwise AND Greater Than Zero
pupil · 430 · lc medium +25 · verified · 80.8% accepted · 1,133 likes · top 92%
Description
The bitwise AND of a collection nums is the AND of all its elements.
- For nums = [1, 5, 3], the AND is 1 & 5 & 3 = 1.
- For nums = [7], the AND is 7.
You are given a positive integer array candidates. Consider all possible subsets (combinations). Return the size of the largest subset whose bitwise AND is 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.
Code
1
2
3