# 2354. Number of Excellent Pairs

• Time: $O(30n) = O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public: long long countExcellentPairs(vector& nums, int k) { constexpr int kMaxBit = 30; // Bits(num1 | num2) + bits(num1 & num2) = bits(num1) + bits(num2) long long ans = 0; vector count(kMaxBit); for (const int num : unordered_set(begin(nums), end(nums))) ++count[__builtin_popcount(num)]; for (int i = 0; i < kMaxBit; ++i) for (int j = 0; j < kMaxBit; ++j) if (i + j >= k) ans += count[i] * count[j]; return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public long countExcellentPairs(int[] nums, int k) { final int kMaxBit = 30; // Bits(num1 | num2) + bits(num1 & num2) = bits(num1) + bits(num2) long ans = 0; long[] count = new long[kMaxBit]; for (final int num : Arrays.stream(nums).boxed().collect(Collectors.toSet())) ++count[Integer.bitCount(num)]; for (int i = 0; i < kMaxBit; ++i) for (int j = 0; j < kMaxBit; ++j) if (i + j >= k) ans += count[i] * count[j]; return ans; } } 
 1 2 3 4 5 6 7 class Solution: def countExcellentPairs(self, nums: List[int], k: int) -> int: count = collections.Counter(map(int.bit_count, set(nums))) return sum(count[i] * count[j] for i in count for j in count if i + j >= k)