[Python3] O(NK) time, O(N + K) space
Intuition\nFirst we observe that the number of set bits in a|b is equal to the sum of the set bits in each of a and b minus the number of set bits in common bet
# Intuition\nFirst we observe that the number of set bits in `a|b` is equal to the sum of the set bits in each of `a` and `b` minus the number of set bits in common between the two. The number of set bits in common between `a` and `b` is exactly the number of set bits in `a&b`. That is:\n\n`count_bits(a | b) = count_bits(a) + count_bits(b) - count_bits(a & b)`\nwhich means:\n`count_bits(a | b) + count_bits(a & b) = count_bits(a) + count_bits(b)`\n\nSo we can just count how many set bits $b$ each number has, and count the number of excellent pairs that can be made by counting how many numbers have at least $k - b$ bits.\n\n# Approach\n1. Iterate over all elements in `set(nums)` (to avoid duplicate numbers).\n2. Count how many bits `b` are in a single `n` and increment the counter `counts[b]`.\n3. Count how many elements have at least `k - b` bits by summing over the tail of the `counts` array.\n4. For each number with at least `k - b` bits, we can form two excellent pairs: `(a, b)` and `(b, a)`. Finally we need to check whether `(n, n)` is also excellent, in which case we have double-counted a single pair and need to subtract one.\n\n# Complexity\n- Time complexity:\n$$O(NK)$$ where $N$ is the length of the array and $K$ is the maximum number of set bits in any given element of the array. $K = 29$ for this problem.\n\n- Space complexity:\n$$O(N + K)$$ since we keep count of how many numbers have $k$ bits, and also need some way to keep track of duplicates. In this case, the construction of `set(nums)` contributes the $N$ term.\n\n# Code\n```\n# 1 <= n <= 10^9 will have at most 29 set bits\nBITS_MAX = 30\n\nclass Solution:\n    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n        # keep array counting how many numbers have n set bits\n        counts = [0]*BITS_MAX\n\n        # keep count of excellent pairs\n        pairs = 0\n        \n        # iterate over all unique numbers in nums\n        for n in set(nums):\n            # count number of bits in n\n            bits = 0\n            b = 1\n            while b <= n:\n                if b&n:\n                    bits += 1\n                b <<= 1\n\n            # increment bits count\n            counts[bits] += 1\n            \n            # count number of pairs this element can be part of (so far)\n            start_index = max(0, k-bits)\n            for b, c in enumerate(counts[start_index:], start_index):\n                # if (n, n) is an excellent pair, don\'t double count\n                if b == bits:\n                    pairs -= 1\n                pairs += 2*c\n\n        return pairs\n```
['Python3']