Simple Python Solution with explanation - Binary Search - 3 lines of code
Basic idea:\n=======\n1. Notice that \n\t(# of bits of x AND y) + (# of bits of x AND y) = (# of bits of x) + (# of bits of y)\n\n2. With knowledge of the relat
Basic idea:\n=======\n1. Notice that \n\t```(# of bits of x AND y) + (# of bits of x AND y) = (# of bits of x) + (# of bits of y)```\n\n2. With knowledge of the relationship in #1, we first ensure all numbers in ```nums``` are unique. Then we create an list whose elements are a tuple of:\n- the number of ```1``` bits for each unique number in ```nums```\n- the number itself\n\n3. For each number with ```bit``` 1 bits, use binary search to find the ```k - bit``` bit value in the list.\n\n**Time complexity** - O(NlogN)\n**Space complexity** - O(N)\n\n**Easier to read version of solution:**\n```\nclass Solution:\n    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n        total = 0\n        nums_set = set(nums)\n        nums1bits = sorted([(Counter(str(bin(num)))[\'1\'], num) for num in nums_set])\n        \n        for bit, num in nums1bits:\n            total += len(nums_set) - bisect_left(nums1bits, (k-bit, 0))\n        \n        return total\n```\n\n**3-lines of code Solution:**\n```\nclass Solution:\n    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n        total, nums_set = 0, set(nums)\n        nums1bits = sorted([(Counter(str(bin(num)))[\'1\'], num) for num in nums_set])\n        return sum([len(nums_set) - bisect_left(nums1bits, (k-bit, 0)) for bit, num in nums1bits])\n```\n\n
[]