Skip to content

2275. Largest Combination With Bitwise AND Greater Than Zero

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 to 1 & 5 & 3 = 1.
  • Also, for nums = [7], the bitwise AND is 7.

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

Solution:

???

class Solution {
    public int largestCombination(int[] candidates) {
        int maxCount = 0;

        for (int i = 0; i < 24; i++){
        // This loop iterates through each bit position from 0 to 23 (representing up to 
         // 2^23. The constraint `1 <= candidates[i] <= 107` means 24 bits are sufficient to represent the largest number, so we only need to check up to the 23rd bit.
            int count = 0;
            for (int num : candidates){
              // Loops through each number in the candidates array.
                if ((num & (1 << i)) != 0){
                    count++;
                }
            }

            maxCount = Math.max(maxCount, count);
        }

        return maxCount;
    }
}

// TC: O(n)
// SC: O(1)

(1 << i) creates a number with a '1' only at bit position i (e.g., 1 << 0 is 1, 1 << 1 is 2, 1 << 2 is 4, etc.).

(num & (1 << i)) != 0 checks if the i-th bit of num is '1'. If it is, then num has a '1' at that bit position.

  • 按位与运算是将每个数字的二进制形式逐位进行“与”操作。例如，数字 5 & 3的按位与计算如下：
5 (0101)
AND
3 (0011)
------
1 (0001)
  • 结果是 1，大于零，所以满足条件。

Wow human!!!

在遍历完所有的位之后，maxCount 会存储每个位上 1 的最大数量。这个值就是符合条件的最大组合的大小。

-> [, , , , ... , _] 只要最大只要有1就满足> 0了