1803. Count Pairs With XOR in a Range

trie is a common technique to deal with bit prefix

intuition 1: to count pairs With XOR between low and high -> count pairs With XOR less than high - count pairs With XOR less than low
intuition 2: bit prefix -> trie

Given upper bound is 5(0101) and num under check is 9(1001).

most significant bit 0 vs 1
- numbers under 0 branch will result in pairs with greater XOR result
- have to go to 1 branch of trie
second significant bit 1 vs 0
- all numbers under 0 branch are qualified since 0^0 = 0 < 1, res += cur['cnt']
- go to 1 branch ...

T = O(n) where n is len(nums)

class Trie:
    
    def __init__(self):
        self.root = {}
    
    def insert(self, num):
        cur = self.root
        for i in reversed(range(15)):
            bit = (num >> i) & 1
            if bit in cur:
                cur[bit]['cnt'] += 1
            else:
                cur[bit] = {'cnt': 1}
            cur = cur.get(bit)
                    
    def count(self, num, limit):
        cur = self.root
        res = 0
        for i in reversed(range(15)):
            target = (limit >> i) & 1
            bit = (num >> i) & 1
            if target:
                if bit in cur:
                    res += cur[bit]['cnt']
                cur = cur.get(bit^1, {})
            else:
                cur = cur.get(bit, {})
        return res
                
class Solution:
    def countPairs(self, nums: List[int], low: int, high: int) -> int:
        res = 0
        trie = Trie()
        for num in nums:
            res += trie.count(num, high+1) - trie.count(num, low)
            trie.insert(num)
        return res

1803. Count Pairs With XOR in a Range - cocoder39/coco39_LC GitHub Wiki