Just count set bits - O(n) Python, 8 lines
We want the number of set bits in (a | b) + number of set bits in (a & b).\n\n Set bits in a | b = (Set bits in a) + (Set bits in b) - (Set bits in a&b).\n\nThe
* We want the number of set bits in `(a | b)` + number of set bits in `(a & b)`.\n\n* Set bits in `a | b` = (Set bits in `a`) + (Set bits in `b`) - (Set bits in `a&b`).\n\nTherefore:\nnumber of set bits in `(a | b)` + number of set bits in `(a & b)` =\nnumber of set bits in `a` + number of set bits in `b`\n****\n**Python**\n```python\nclass Solution:\n\n    def countExcellentPairs(self, nums: List[int], k: int) -> int:\n        count_set_bits = defaultdict(set)\n        for x in nums:\n            count_set_bits[x.bit_count()].add(x)\n\n        answer = 0\n        for nbits1, nbits2 in product(count_set_bits, count_set_bits):\n            if nbits1 + nbits2 >= k:\n                answer += len(count_set_bits[nbits1]) * len(count_set_bits[nbits2])\n        return answer\n```\n`O(n)` time and space, as each number has at most 30 bits.
[]