Find the largest subset of numbers whose bitwise AND is greater than zero.
You are given an array of integers. Choose any non-empty subset of the array and compute the bitwise AND of all numbers in that subset.
Return the maximum size of a subset whose bitwise AND is strictly greater than zero.
A subset may contain any elements from the array, but each selected element must come from a different position in the array.
Input Format
- An integer array
candidates. - Each value is a non-negative integer.
Output Format
- Return the size of the largest subset whose bitwise AND is greater than
0.
Constraints
1 <= candidates.length <= $10^{5}$0 <= candidates[i] <= $10^{9}$- The answer is an integer between
1andcandidates.length. - The array contains at least one valid non-empty subset with bitwise AND greater than
0.
Example 1
Input
candidates = [16,17,71,62,12,24,14]
Output
4
Explanation
The best choice is a subset of 4 numbers that all share bit 4 (value 16), such as [16,17,24,14]. Their bitwise AND is 16, which is greater than 0.
Example 2
Input
candidates = [8,8]
Output
2
Explanation
Both numbers have the same set bit, so the AND of the whole array is 8, and the largest valid subset has size 2.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.