[LeetCode] 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

按位与结果大于零的最长组合。

对数组 nums 执行 按位与 相当于对数组 nums 中的所有整数执行 按位与 。

例如，对 nums = [1, 5, 3] 来说，按位与等于 1 & 5 & 3 = 1 。
同样，对 nums = [7] 而言，按位与等于 7 。
给你一个正整数数组 candidates 。计算 candidates 中的数字每种组合下 按位与 的结果。 candidates 中的每个数字在每种组合中只能使用 一次 。

返回按位与结果大于 0 的 最长 组合的长度。

思路

这是一道位运算的题。因为题目要求我们找到是一个数字组合，这个组合需要满足的条件是他们的 AND 操作要最大。但是因为这个组合里的数字个数不定，所以没法用类似 backtracking 那样的方法去枚举；且问的是 AND 操作的最大值，所以思路只能往 bit manipulation 上靠。

假如所有数字可以用 8 个 digit 表达完 (0000 0000)，那么使 AND 的结果最大的方式就是最高位最好都是 1。那么我们可以从二进制的低位遍历到高位（从右往左看），统计一下每个数字的二进制表达里每个位置上的 1 的情况，用一个 map 记录一下。在遍历过程中记录出现 1 的最大次数。因为是从右往左扫描的所以最大次数越往左，结果越大。

复杂度

时间O(n) - candidates 数组遍历一次
空间O(1)

代码

Java实现

class Solution {
    public int largestCombination(int[] candidates) {
        int[] map = new int[24];
		int max = 0;
		for (int candidate : candidates) {
			for (int i = 0; i < 24; i++) {
				if ((candidate & (1 << i)) > 0) {
					map[i]++;
					max = Math.max(max, map[i]);
				}
			}
		}
		return max;
    }
}