2275. Largest Combination With Bitwise AND

Problem

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.

Solution

相当于将各个数字进行掩码操作,计算各个数组的同一个位上1的数量即可。

bin[]数组记录各个数字的各个位上的1的数量。
如果当前数字与1进行掩码操作后等于1,则将该位数量加一。
然后将当前数字向右移动一位,直至将所有的位都统计完。

最后返回各个位上的最大值即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int largestCombination(int[] candidates) {
int[] bin = new int[31];
int res = 0;
for(int candidate : candidates){
int count = 0;
while(count < 31){
if((candidate & 1) == 1){
bin[count]++;
}
candidate = candidate >> 1;
count++;
}
}
for(int time : bin){
res = Math.max(res, time);
}
return res;
}
}
Author

Xander

Posted on

2022-05-15

Updated on

2022-05-14

Licensed under

Comments