Count Pairs With XOR in a Range - Video Solutions

Problem Overview: You are given an integer array nums and two values low and high. The task is to count pairs (i, j) where i < j and the XOR of the pair nums[i] ^ nums[j] lies within the range [low, high]. A direct comparison of every pair works but becomes too slow for large inputs.

Approach 1: Brute Force Pair Enumeration (O(n²) time, O(1) space)

The simplest solution checks every pair in the array. Iterate with two nested loops, compute x = nums[i] ^ nums[j], and increment the answer if low ≤ x ≤ high. XOR is a constant-time bit operation, so the main cost comes from examining all n(n−1)/2 pairs. This approach works well for small arrays and helps validate correctness during debugging. However, for large inputs the quadratic complexity becomes the bottleneck.

Approach 2: Bitwise Trie with Range Counting (O(n · B) time, O(n · B) space)

The optimized method uses a binary Trie to count how many previous numbers produce a valid XOR with the current number. Instead of directly counting XOR values inside [low, high], compute:

count(xor ≤ high) − count(xor < low).

Insert numbers into a bitwise Trie while iterating through the array. Each node represents a bit (0 or 1). For a number num, traverse the Trie from the most significant bit to the least. At each level, use the bit of num and the corresponding bit of the limit (high or low−1) to decide whether entire branches can be counted or must be explored further. This pruning works because XOR results depend only on bit differences.

If the current limit bit is 1, you can add the count of nodes that keep the XOR bit smaller and continue exploring the alternative branch. If the limit bit is 0, you must stay on the branch that keeps the XOR result within the constraint. The Trie stores counts of numbers passing through each node, making it possible to accumulate valid pair counts efficiently.

This technique processes each number in about B steps, where B is the number of bits (usually 15–16 for this problem). It reduces the complexity from quadratic to near-linear while maintaining deterministic performance.

The solution relies heavily on bit manipulation and a binary Trie structure applied over an array. The key insight is converting a range query into two prefix counts.

Recommended for interviews: Start by explaining the brute force method to demonstrate understanding of the XOR condition. Then transition to the Trie-based counting strategy. Interviewers typically expect the optimized approach because it shows comfort with bitwise reasoning, prefix counting, and specialized data structures.