Count Pairs With XOR in a Range: Trie Bit Manipulation

You are given an integer array nums and two integers low and high. You need to count the number of pairs (i, j) where i < j and low <= nums[i] XOR nums[j] <= high. This is LeetCode 1803: Count Pairs With XOR in a Range.

The brute force approach checks every pair in O(n^2) time. With nums up to length 20,000 and values up to 20,000, that is too slow. You need a data structure that can efficiently count how many existing numbers produce an XOR within a given range when paired with a new number. That data structure is a bitwise trie.

Why this problem matters

This problem sits at the intersection of two important patterns: trie-based queries and bit manipulation. Most developers are familiar with tries for string prefix matching, but using a trie on the binary representation of integers is a different skill entirely. This technique shows up in problems involving XOR maximization, XOR range queries, and bitwise nearest-neighbor searches. Mastering it gives you a reusable tool for an entire class of bitwise problems.

The key insight

The core trick is to decompose the range query into two threshold queries. Instead of counting pairs where low <= XOR <= high directly, you compute countBelow(high + 1) - countBelow(low). This gives you exactly the pairs in the range [low, high].

The countBelow(threshold) function uses a bitwise trie. For each number in the array, you walk the trie from the most significant bit to the least significant bit. At each level, you look at the corresponding bit of the threshold:

• If the threshold bit is 1, then all numbers in the "same direction" branch produce an XOR with that bit equal to 0. Their XOR at this bit is guaranteed to be less than the threshold's bit, so every number in that subtree forms a valid pair. Add the count of that subtree and continue down the "different direction" branch (where the XOR bit would be 1, matching the threshold bit, so you need to keep checking lower bits).
• If the threshold bit is 0, then going the "different direction" would produce an XOR bit of 1, which already exceeds the threshold at this position. You must stay on the "same direction" branch.

After querying, you insert the current number into the trie. Processing numbers left to right and querying before inserting ensures each pair (i, j) with i < j is counted exactly once.

The solution

class Solution:
    def countPairs(self, nums, low, high):
        def count_below(threshold):
            root = {}
            total = 0
            for num in nums:
                node = root
                curr = root
                for bit in range(14, -1, -1):
                    num_bit = (num >> bit) & 1
                    thr_bit = (threshold >> bit) & 1
                    if thr_bit == 1:
                        same = num_bit
                        if same in node:
                            total += node[same].get("#", 0)
                        diff = 1 - num_bit
                        if diff not in node:
                            break
                        node = node[diff]
                    else:
                        same = num_bit
                        if same not in node:
                            break
                        node = node[same]
                curr = root
                for bit in range(14, -1, -1):
                    b = (num >> bit) & 1
                    if b not in curr:
                        curr[b] = {"#": 0}
                    curr[b]["#"] = curr[b].get("#", 0) + 1
                    curr = curr[b]
            return total

        return count_below(high + 1) - count_below(low)

The trie is represented as nested dictionaries. Each node uses integer keys 0 and 1 for its children, and a special key "#" to store the count of numbers passing through that node. The count_below function processes every number twice in each call: once to query valid pairs, once to insert into the trie.

There is a cleaner version that separates the trie into its own class. Let's look at that approach, since it makes the logic easier to follow.

class Solution:
    def countPairs(self, nums, low, high):
        return self.count_below(nums, high + 1) - self.count_below(nums, low)

    def count_below(self, nums, threshold):
        trie = [[None, None, 0]]
        total = 0
        for num in nums:
            node = 0
            for bit in range(14, -1, -1):
                num_bit = (num >> bit) & 1
                thr_bit = (threshold >> bit) & 1
                if thr_bit == 1:
                    same = num_bit
                    if trie[node][same] is not None:
                        total += trie[trie[node][same]][2]
                    diff = 1 - num_bit
                    if trie[node][diff] is None:
                        break
                    node = trie[node][diff]
                else:
                    same = num_bit
                    if trie[node][same] is None:
                        break
                    node = trie[node][same]
            node = 0
            for bit in range(14, -1, -1):
                b = (num >> bit) & 1
                if trie[node][b] is None:
                    trie.append([None, None, 0])
                    trie[node][b] = len(trie) - 1
                node = trie[node][b]
                trie[node][2] += 1
        return total

Each trie node is a list [left_child, right_child, count]. This version avoids dictionary overhead and runs faster in practice.

Visual walkthrough

Here is how the algorithm processes each number: decompose the range into two threshold queries, build a trie incrementally, and count valid pairs at each step.

The key moment in each step is the decision at every bit level. When the threshold bit is 1, you get to "bank" all the counts from the same-direction subtree, because every number there is guaranteed to produce an XOR below the threshold. Then you explore the other branch to continue narrowing down.

Complexity analysis

Time: O(n * B) where n is the array length and B is the number of bits (15 for constraints up to 2^15). Each number requires a trie query and a trie insertion, both O(B). The count_below function is called twice, so the total is O(2 * n * B) = O(n * B).

Space: O(n * B) for the trie nodes. In the worst case, each of the n numbers creates B new nodes (when no prefixes are shared). In practice, many numbers share common bit prefixes, so the trie is smaller.

The building blocks

1. Bitwise trie for XOR queries

A bitwise trie stores numbers by their binary representation, one bit per level. The root is the most significant bit, and leaves correspond to the least significant bit. Each node tracks how many numbers pass through it using a count field.

trie = [[None, None, 0]]

def insert(num):
    node = 0
    for bit in range(14, -1, -1):
        b = (num >> bit) & 1
        if trie[node][b] is None:
            trie.append([None, None, 0])
            trie[node][b] = len(trie) - 1
        node = trie[node][b]
        trie[node][2] += 1

This is the same trie structure used in "Maximum XOR of Two Numbers in an Array" (LeetCode 421). Once you can write this insertion from memory, you have the foundation for all bitwise trie problems.

2. Counting pairs below a threshold

The query walks the trie in parallel with the threshold's bits. At each level where the threshold bit is 1, you add the count of the subtree that guarantees a smaller XOR and continue exploring the branch that might still produce valid pairs.

def count_less(num, threshold):
    node = 0
    result = 0
    for bit in range(14, -1, -1):
        num_bit = (num >> bit) & 1
        thr_bit = (threshold >> bit) & 1
        if thr_bit == 1:
            same = num_bit
            if trie[node][same] is not None:
                result += trie[trie[node][same]][2]
            diff = 1 - num_bit
            if trie[node][diff] is None:
                break
            node = trie[node][diff]
        else:
            if trie[node][num_bit] is None:
                break
            node = trie[node][num_bit]
    return result

This pattern of "bank the safe side, explore the boundary" appears whenever you need to count elements below a bitwise threshold. It is the bitwise analog of counting elements in a range using a balanced BST.

Edge cases

• All elements equal: every XOR is 0, so count pairs only if 0 is in the range [low, high]
• Single element: no pairs possible, return 0
• low = 0: include pairs where XOR equals 0 (identical elements)
• All pairs valid: when the range [low, high] covers all possible XOR values, the answer is n * (n - 1) / 2
• Large numbers: ensure the bit length covers the maximum value in both nums and high (15 bits for constraints up to 20,000)

From understanding to recall

The bitwise trie approach can feel complex at first glance, but it breaks down into just two operations: inserting a number bit by bit, and walking the trie to count pairs below a threshold. The range decomposition into countBelow(high + 1) - countBelow(low) is a standard technique you have likely seen in prefix sum problems. The real challenge is internalizing the bit-by-bit trie traversal, where you decide at each level whether to bank counts and switch branches or stay on the same path. Spaced repetition helps you practice these decisions until the logic becomes automatic. After a few reps, you will not need to rederive the algorithm during an interview.

Related posts

• Implement Trie - The foundational trie data structure that this problem builds on
• Number of 1 Bits - Understanding bit manipulation basics needed for XOR operations
• Single Number - The classic XOR cancellation pattern that builds intuition for XOR properties

CodeBricks breaks this problem into its bitwise trie insertion and threshold counting building blocks, then drills them independently with spaced repetition. You practice each piece from scratch until the trie traversal and the "bank and explore" counting pattern are second nature. When a bitwise trie problem appears in your interview, you do not hesitate. You build the trie, walk the bits, and count the pairs.