LeetCode 1803 - Count Pairs With XOR in a Range

The problem gives us an integer array nums and two integers, low and high. We need to count how many index pairs (i, j) satisfy two conditions: - i < j - low <= nums[i] XOR nums[j] <= high The XOR operation compares bits between two numbers.

leetcodehardarraybit-manipulationtrie

LeetCode Problem 1803

Difficulty: 🔴 Hard
Topics: Array, Bit Manipulation, Trie

Solution

LeetCode 1803 - Count Pairs With XOR in a Range

Problem Understanding

The problem gives us an integer array nums and two integers, low and high. We need to count how many index pairs (i, j) satisfy two conditions:

  • i < j
  • low <= nums[i] XOR nums[j] <= high

The XOR operation compares bits between two numbers. For each bit position:

  • If the bits are different, the result bit becomes 1
  • If the bits are the same, the result bit becomes 0

The task is not asking us to return the pairs themselves. We only need the total count.

For example, if:

nums = [1,4,2,7]
low = 2
high = 6

then:

1 XOR 4 = 5
1 XOR 2 = 3
1 XOR 7 = 6

All of these values lie within [2, 6], so they contribute to the answer.

The constraints are important:

  • nums.length <= 2 * 10^4
  • nums[i] <= 2 * 10^4

A naive solution that checks every pair would require approximately:

(2 * 10^4)^2 = 4 * 10^8

comparisons in the worst case, which is too slow.

The values are also relatively small, which strongly suggests that a bitwise data structure may help. Since XOR is fundamentally a bit operation, a binary trie becomes a natural candidate.

Several edge cases are worth noting immediately:

  • Arrays with only one element should return 0
  • Multiple identical values may produce XOR 0
  • The range may include almost all possible XOR values
  • The range boundaries are inclusive
  • We must avoid double counting pairs

The problem guarantees valid inputs, so we do not need to handle invalid ranges or empty arrays.

Approaches

Brute Force Approach

The simplest solution is to examine every possible pair (i, j) where i < j.

For each pair:

  1. Compute nums[i] XOR nums[j]
  2. Check whether the XOR result lies within [low, high]
  3. Increment the answer if it does

This works because it directly follows the problem definition.

However, the time complexity is too high. There are O(n^2) pairs, and with n = 20,000, this becomes infeasible.

Key Insight for the Optimal Solution

The important observation is that instead of directly counting XOR values inside a range, we can compute:

count(XOR <= high) - count(XOR < low)

More specifically:

count(low <= XOR <= high)
=
count(XOR <= high) - count(XOR <= low - 1)

So the problem reduces to efficiently counting how many previous numbers produce XOR values less than or equal to a limit.

This is where a binary trie helps.

A binary trie stores numbers bit by bit. While processing a number x, we can efficiently count how many previously inserted numbers satisfy:

x XOR y < limit

The trie allows us to evaluate this condition one bit at a time.

Because numbers are at most 2 * 10^4, they fit within 15 bits. Using a fixed number of bits keeps operations efficient.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks every pair directly
Optimal Trie Solution O(n × B) O(n × B) Uses binary trie, where B is number of bits

Here, B = 15 or 16, which is effectively constant.

Algorithm Walkthrough

Step 1: Transform the Range Query

Instead of directly counting XOR values inside [low, high], compute:

countPairsLessThan(high + 1) - countPairsLessThan(low)

Where:

countPairsLessThan(limit)

returns the number of pairs whose XOR is strictly less than limit.

This transformation simplifies the logic significantly.

Step 2: Build a Binary Trie

A binary trie stores bits from the most significant bit down to the least significant bit.

Each trie node contains:

  • Two children:

  • 0

  • 1

  • A count representing how many numbers pass through that node

For example, the number 5:

0101

would be inserted bit by bit.

Step 3: Process Numbers One by One

We iterate through nums.

For each number x:

  1. Query the trie to count how many previously inserted numbers satisfy:
x XOR y < limit
  1. Add that count to the answer
  2. Insert x into the trie

This guarantees:

  • Every pair is counted exactly once
  • Only earlier elements are considered

Step 4: Query Logic

The query works bit by bit.

Suppose we are examining bit k.

Let:

  • xBit be the current bit of x
  • limitBit be the current bit of limit

There are two cases.

Case 1: limitBit == 1

If the limit bit is 1, then:

  • Choosing XOR bit 0 keeps us strictly below the limit at this position
  • Choosing XOR bit 1 means we remain equal so far and must continue checking lower bits

So:

  • Add all valid branches producing XOR bit 0
  • Continue traversal on the branch producing XOR bit 1

Case 2: limitBit == 0

If the limit bit is 0, we cannot exceed it.

Therefore:

  • We are forced to choose XOR bit 0
  • Continue traversal only on that branch

This bitwise reasoning is what makes the trie efficient.

Step 5: Compute Final Answer

Finally:

answer =
countPairsLessThan(high + 1)
-
countPairsLessThan(low)

This gives the count of XOR values inside the inclusive range.

Why it works

The trie always contains exactly the numbers that appear before the current index, so every pair satisfies i < j.

The query logic counts exactly those numbers whose XOR with the current number is less than the specified limit. Since XOR comparison can be evaluated lexicographically from the most significant bit downward, processing bits greedily produces the correct count.

Subtracting two prefix counts isolates the desired range.

Python Solution

from typing import List

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0

class Solution:
    def countPairs(self, nums: List[int], low: int, high: int) -> int:
        MAX_BIT = 15

        def count_less_than(limit: int) -> int:
            root = TrieNode()
            total_pairs = 0

            def insert(num: int) -> None:
                node = root

                for bit in range(MAX_BIT, -1, -1):
                    current_bit = (num >> bit) & 1

                    if current_bit not in node.children:
                        node.children[current_bit] = TrieNode()

                    node = node.children[current_bit]
                    node.count += 1

            def query(num: int) -> int:
                node = root
                count = 0

                for bit in range(MAX_BIT, -1, -1):
                    if node is None:
                        break

                    num_bit = (num >> bit) & 1
                    limit_bit = (limit >> bit) & 1

                    if limit_bit == 1:
                        same_branch = node.children.get(num_bit)

                        if same_branch:
                            count += same_branch.count

                        node = node.children.get(1 - num_bit)
                    else:
                        node = node.children.get(num_bit)

                return count

            for num in nums:
                total_pairs += query(num)
                insert(num)

            return total_pairs

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

The implementation starts by defining a trie node. Each node stores:

  • Child pointers for bits 0 and 1
  • A count of how many numbers pass through that node

The helper function count_less_than(limit) computes how many pairs have XOR strictly smaller than limit.

Inside this function:

  • insert() adds a number into the trie bit by bit
  • query() counts how many previously inserted numbers satisfy:
num XOR previous < limit

The query processes bits from most significant to least significant. At each step, it uses the current limit bit to decide whether an entire subtree can be counted immediately or whether traversal must continue.

The main loop processes numbers sequentially:

  • Query first
  • Insert afterward

This guarantees that only earlier indices are counted.

Finally, the main function converts the inclusive range into two prefix queries:

count(< high + 1) - count(< low)

which produces the required answer.

Go Solution

package main

type TrieNode struct {
	children [2]*TrieNode
	count    int
}

func countPairs(nums []int, low int, high int) int {
	const MAX_BIT = 15

	countLessThan := func(limit int) int {
		root := &TrieNode{}
		totalPairs := 0

		insert := func(num int) {
			node := root

			for bit := MAX_BIT; bit >= 0; bit-- {
				currentBit := (num >> bit) & 1

				if node.children[currentBit] == nil {
					node.children[currentBit] = &TrieNode{}
				}

				node = node.children[currentBit]
				node.count++
			}
		}

		query := func(num int) int {
			node := root
			count := 0

			for bit := MAX_BIT; bit >= 0; bit-- {
				if node == nil {
					break
				}

				numBit := (num >> bit) & 1
				limitBit := (limit >> bit) & 1

				if limitBit == 1 {
					sameBranch := node.children[numBit]

					if sameBranch != nil {
						count += sameBranch.count
					}

					node = node.children[1-numBit]
				} else {
					node = node.children[numBit]
				}
			}

			return count
		}

		for _, num := range nums {
			totalPairs += query(num)
			insert(num)
		}

		return totalPairs
	}

	return countLessThan(high+1) - countLessThan(low)
}

The Go implementation follows the same logic as the Python version, but uses fixed-size child arrays instead of dictionaries.

This is efficient because each node only has two possible children.

Go-specific details include:

  • Pointer-based trie nodes
  • Explicit nil checks during traversal
  • Fixed array [2]*TrieNode for child references
  • Integer operations remain safe because the maximum answer fits within standard int

Worked Examples

Example 1

Input:

nums = [1,4,2,7]
low = 2
high = 6

We compute:

count(< 7) - count(< 2)

Counting XOR < 7

Current Number Previous Numbers in Trie Valid XORs Added Count
1 [] none 0
4 [1] 1 XOR 4 = 5 1
2 [1,4] 2 XOR 1 = 3, 2 XOR 4 = 6 2
7 [1,4,2] 7 XOR 1 = 6, 7 XOR 4 = 3, 7 XOR 2 = 5 3

Total:

6

Counting XOR < 2

No pair produces XOR less than 2.

So:

6 - 0 = 6

Final answer:

6

Example 2

Input:

nums = [9,8,4,2,1]
low = 5
high = 14

We compute:

count(< 15) - count(< 5)

Counting XOR < 15

Almost every pair qualifies except XOR 15 itself.

Pair XOR Counted?
9,8 1 No
9,4 13 Yes
9,2 11 Yes
9,1 8 Yes
8,4 12 Yes
8,2 10 Yes
8,1 9 Yes
4,2 6 Yes
4,1 5 Yes
2,1 3 No

Count:

8

Counting XOR < 5

Only:

9 XOR 8 = 1
2 XOR 1 = 3

Count:

2

Subtracting:

10 - 2 = 8

Final answer:

8

Complexity Analysis

Measure Complexity Explanation
Time O(n × B) Each insert and query processes B bits
Space O(n × B) Trie may store up to B nodes per number

Since B is at most 16, the algorithm is effectively linear in practice.

Each number is inserted once and queried once. Both operations traverse the trie from the most significant bit to the least significant bit, so they require constant work per bit.

The trie size grows proportionally to the number of inserted numbers times the number of bits.

Test Cases

sol = Solution()

# Provided example 1
assert sol.countPairs([1, 4, 2, 7], 2, 6) == 6

# Provided example 2
assert sol.countPairs([9, 8, 4, 2, 1], 5, 14) == 8

# Single element, no pairs possible
assert sol.countPairs([5], 1, 10) == 0

# Two identical numbers, XOR = 0
assert sol.countPairs([3, 3], 0, 0) == 1

# Two identical numbers outside range
assert sol.countPairs([3, 3], 1, 5) == 0

# All pairs valid
assert sol.countPairs([1, 2, 3], 0, 10) == 3

# No valid pairs
assert sol.countPairs([1, 1, 1], 5, 10) == 0

# Large XOR values
assert sol.countPairs([16384, 8192, 4096], 1, 30000) == 3

# Boundary range with exact match
assert sol.countPairs([1, 2], 3, 3) == 1

# Mixed duplicates
assert sol.countPairs([5, 5, 5, 5], 0, 0) == 6

# Increasing sequence
assert sol.countPairs([1, 2, 4, 8], 1, 15) == 6

# XOR exactly on upper boundary
assert sol.countPairs([1, 6], 7, 7) == 1

Test Summary

Test Why
[1,4,2,7] Verifies standard mixed XOR values
[9,8,4,2,1] Verifies broader range handling
Single element Ensures no invalid pair counting
Duplicate values with XOR 0 Tests equality edge case
Duplicate values outside range Ensures filtering works
All pairs valid Confirms full counting
No valid pairs Confirms zero handling
Large values Tests higher bit positions
Exact boundary match Verifies inclusive range
Many duplicates Tests combinational counting
Increasing powers of two Exercises bit structure
XOR equal to high Verifies upper bound inclusion

Edge Cases

Single Element Array

If the array contains only one number, there are no valid pairs because the condition requires i < j.

A naive implementation might accidentally count self-pairs if insertion and querying are done in the wrong order.

This implementation avoids that by querying before insertion. The current number is never matched against itself.

Duplicate Numbers

When two numbers are identical:

x XOR x = 0

This can easily create many valid pairs when the range includes zero.

The trie correctly handles duplicates because each trie node stores a count of how many numbers pass through it. Multiple identical numbers increment the same paths, allowing all combinations to be counted.

Inclusive Range Boundaries

The problem uses:

low <= XOR <= high

Inclusive bounds are a common source of off-by-one errors.

The implementation carefully converts the range into:

count(< high + 1) - count(< low)

This transformation ensures that both boundaries are handled correctly without special-case logic.