LeetCode Solutions Blog

Count Pairs With XOR in a Range

Number: 1907

Difficulty: Hard

Paid? No

Companies: Google, Vimeo

Problem Description

Given an integer array nums and two integers low and high, return the number of nice pairs. A nice pair (i, j) must satisfy 0 <= i < j < nums.length and low <= (nums[i] XOR nums[j]) <= high.

Key Insights

The brute-force solution would check every pair in O(n^2), which is too slow when n can be 20000.
Use a trie (bitwise tree) to store numbers seen so far. This allows us to count how many numbers yield an XOR value below a given limit when XORed with the current number.
To count pairs with XOR in the range [low, high], compute countPairs(high) - countPairs(low - 1) where countPairs(limit) finds the number of pairs with XOR less than or equal to limit.
Each number is processed bit-by-bit (up to around 15 bits, since nums[i] and limits are up to 20000) so the per-number work is constant.

Space and Time Complexity

Time Complexity: O(n * B) where B is the number of bits (approximately 15), essentially O(n).
Space Complexity: O(n * B) for the trie storage, which is acceptable for the given constraints.

Solution

We use a bitwise trie to store binary representations of previously seen numbers. For each number in the array, we count how many previously inserted numbers yield an XOR value with this number less than or equal to a certain limit (first high and then low-1). The count difference gives us the number of pairs within the desired range. The trie nodes store a count of how many numbers pass through that node (for the corresponding bit 0 or 1). When searching for the count of numbers that satisfy the XOR condition, we compare bits of the current number and the limit and traverse the trie accordingly. This approach significantly reduces the time compared to comparing every pair.

Code Solutions

# Python solution using a bitwise Trie.
class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0

class Trie:
    def __init__(self):
        self.root = TrieNode()
        self.BIT_LIMIT = 15  # Since nums[i] and limits are <= 20000
    
    def insert(self, num):
        node = self.root
        for i in range(self.BIT_LIMIT, -1, -1):
            bit = (num >> i) & 1
            if bit not in node.children:
                node.children[bit] = TrieNode()
            node = node.children[bit]
            node.count += 1
            
    def countLessOrEqual(self, num, limit):
        node = self.root
        count = 0
        for i in range(self.BIT_LIMIT, -1, -1):
            if not node:
                break
            numBit = (num >> i) & 1
            limitBit = (limit >> i) & 1
            if limitBit == 1:
                # If limitBit is 1, we can take all numbers from the branch equal to numBit
                if numBit in node.children:
                    count += node.children[numBit].count
                # Then we move to the alternative branch for further restrictions.
                node = node.children.get(1 - numBit, None)
            else:
                # If limitBit is 0, we must go to the branch that exactly matches numBit.
                node = node.children.get(numBit, None)
        return count

def countPairs(nums, limit):
    trie = Trie()
    count = 0
    # Process each number and count numbers already seen that satisfy the XOR condition.
    for num in nums:
        count += trie.countLessOrEqual(num, limit)
        trie.insert(num)
    return count

def countPairsWithXORInRange(nums, low, high):
    # Use inclusion-exclusion: count pairs with XOR <= high minus pairs with XOR < low.
    return countPairs(nums, high) - countPairs(nums, low - 1)

# Example Usage:
if __name__ == '__main__':
    nums = [1,4,2,7]
    low = 2
    high = 6
    print(countPairsWithXORInRange(nums, low, high))  # Expected output: 6