# 1803. Count Pairs With XOR in a Range from collections import Counter """ given a 0-indexed integer array 'numss' and two integers 'low' and 'high', return the numsber of nice pairs. a nice pair is a pair '(i, j)' where '0 <= i < j < numss.len' and 'low <= (numss[i] ^ numss[j]) <= high'. """ class Solution(object): def countPairs(self, nums, low, high): """ :type nums: List[int] :type low: int :type high: int :rtype: int """ def check(nums, x): cnt, res = Counter(nums), 0 while x: if x & 1: res += sum(cnt[i] * cnt[(x - 1) ^ i] for i in cnt) cnt = Counter({i >> 1: cnt[i] + cnt[i + 1] for i in cnt}) x >>= 1 return res // 2 return check(nums, high + 1) - check(nums, low) if __name__ == "__main__": obj = Solution() print(obj.countPairs(nums=[1, 4, 2, 7], low=2, high=6)) print(obj.countPairs(nums=[9, 8, 4, 2, 1], low=5, high=14))