Leetcode

Posted on

Original Problem can be found here.

For number and , we can found that ones in plus ones in , equals to the ones in plus ones in .

E.g. for and , their binary formats are and , (3 & 2).bit_count() equals to 1, (3 | 2).bit_count() equals to 2.

Thus, for this problem, we need to find any pair of numbers where the sum of their bit_count() is greater or equal than . We can use a binary search algorithm to achieve this.

Time Complexity: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import bisect

class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:
        res = 0
        nums = set(nums)

        def bitcount(x: int):
            c = 0
            while x:
                c += x & 1
                x >>= 1
            return c

        length = len(nums)
        binl = sorted([bitcount(i) for i in nums])
        for ii, i in enumerate(binl):
            pos = bisect.bisect_left(binl, k - i)
            t = length - pos
            res += t
        
        return res