[Python3] Sorting Hamming Weights + Binary Search With Detailed Explanations
I have to say that the problem description is a little bit confusing, so let\'s clarify it together.\n\nObservations & Explanations\n1. The problem asks for the
I have to say that the problem description is a little bit confusing, so let\'s clarify it together.\n\n**Observations & Explanations**\n1. The problem asks for the number of **distinct** excellent pairs, therefore duplicated `num` in the `nums` array does not matter and we only need to look at unique `num` appeared in the array.\n2. The excellent pair **can** include a `num` paired with itself.\n3. For any pair of bits `(b1, b2)`, where `b1` and `b2` can take `0` or `1`, we have `(b1 OR b2) + (b1 AND b2) = b1 + b2`. Specifically,\n* \t`(0 OR 0) + (0 AND 0) = 0 + 0 = 0 = 0 + 0`;\n* \t`(0 OR 1) + (0 AND 1) = 1 + 0 = 1 = 0 + 1`;\n* \t`(1 OR 0) + (1 AND 0) = 1 + 0 = 1 = 1 + 0`;\n* \t`(1 OR 1) + (1 AND 1) = 1 + 1 = 2 = 1 + 1`.\n4. From above, we have that for any pair `(num1, num2)`, the sum of the number of set bits in `num1 OR num2` and `num1 AND num2` is the same as the number of set bits in `num1` and `num2` themselves. Therefore, we don\'t actually need to calculate the `OR/AND` operations but just need to store the hamming weight, `hamming`, for each of the unique `num` in the `nums` array.\n5. After we have the `hamming` array, the problem essentially becomes a "Two Sum Greater Than K" type of problem, where we can sort the `hamming` array first, and then use a binary search to get the number of "Excellent Pairs" in the original `nums` array.\n\n**Complexity Analysis**\nTime: `O(NlogN + NlogM)`, where `M = max(nums)`.\nSpace: `O(N)`, for storing the hamming weights;\n\n**Solution**\nPlease upvote if you find this solution helpful. Thanks!\n```\nclass Solution:\n    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n        hamming = sorted([self.hammingWeight(num) for num in set(nums)])\n        ans = 0\n        for h in hamming:\n            ans += len(hamming) - bisect.bisect_left(hamming, k - h)\n        return ans\n        \n    def hammingWeight(self, n):\n        ans = 0\n        while n:\n            n &= (n - 1)\n            ans += 1\n        return ans\n```\n\n**Remark 1**: Above is a solution (~2000 ms) implemented with binary search after sorting the `hamming` array. One can also use two pointers to get the number of "Excellent Pairs" in the original `nums` array. However, the time complexity would not change since sorting the `hamming` array requires `O(NlogN)` time complexity.\n\n**Remark 2**: Shorter and faster solution (1435 ms) using Python 3.10\'s [new built-in method](https://docs.python.org/3/library/stdtypes.html#int.bit_count) `int.bit_count()`.\n```\nclass Solution:\n    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n        hamming = sorted([num.bit_count() for num in set(nums)])\n        ans = 0\n        for h in hamming:\n            ans += len(hamming) - bisect.bisect_left(hamming, k - h)\n        return ans\n```\n\n**Remark 3**: Another short and fast solution (1129 ms) using `Counter` (hashmap).\n```\nclass Solution:\n    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n        hamming = Counter([num.bit_count() for num in set(nums)])\n        ans = 0\n        for h1 in hamming:\n            for h2 in hamming:\n                if h1 + h2 < k:\n                    continue\n                ans += hamming[h1] * hamming[h2]\n        return ans\n```
['Binary Tree', 'Python', 'Python3']