2275. Largest Combination With Bitwise AND Greater Than Zero

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. Compute the bitwise AND for all possible combinations of elements in the candidates array.

Return the size of the largest combination of candidates with a bitwise AND greater than 0.

https://leetcode.cn/problems/largest-combination-with-bitwise-and-greater-than-zero/

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 <= 10⁵
• 1 <= candidates[i] <= 10⁷

Test Cases

1
2

class Solution:
    def largestCombination(self, candidates: List[int]) -> int:

1
2
3
4
5
6
7
8
9
10
11
12

import pytest

from solution import Solution


@pytest.mark.parametrize('candidates, expected', [
    ([16,17,71,62,12,24,14], 4),
    ([8,8], 2),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, candidates, expected):
    assert sol.largestCombination(candidates) == expected

Thoughts

对于每一个可能的二进制位，统计所有数字有多少个在这一位是 1，这些数字做按位与之后的结果一定不为零。最终看哪一位对应的数字数量最多即可。

Code

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def largestCombination(self, candidates: list[int]) -> int:
        counts = [0] * 24 # log2(1e7, 2)
        for num in candidates:
            i = 0
            while num > 0:
                counts[i] += num & 1
                num >>= 1
                i += 1

        return max(counts)

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章