Given a (0-indexed) integer array nums and two integers low and high, return the number of nice pairs.
A nice pair is a pair (i, j) where 0 <= i < j < nums.length and low <= (nums[i] XOR nums[j]) <= high.
Example 1:
Input: nums = [1,4,2,7], low = 2, high = 6
Output: 6
Explanation: All nice pairs (i, j) are as follows:
- (0, 1): nums[0] XOR nums[1] = 5
- (0, 2): nums[0] XOR nums[2] = 3
- (0, 3): nums[0] XOR nums[3] = 6
- (1, 2): nums[1] XOR nums[2] = 6
- (1, 3): nums[1] XOR nums[3] = 3
- (2, 3): nums[2] XOR nums[3] = 5
Example 2:
Input: nums = [9,8,4,2,1], low = 5, high = 14 Output: 8 Explanation: All nice pairs (i, j) are as follows: - (0, 2): nums[0] XOR nums[2] = 13 - (0, 3): nums[0] XOR nums[3] = 11 - (0, 4): nums[0] XOR nums[4] = 8 - (1, 2): nums[1] XOR nums[2] = 12 - (1, 3): nums[1] XOR nums[3] = 10 - (1, 4): nums[1] XOR nums[4] = 9 - (2, 3): nums[2] XOR nums[3] = 6 - (2, 4): nums[2] XOR nums[4] = 5
Constraints:
1 <= nums.length <= 2 * 1041 <= nums[i] <= 2 * 1041 <= low <= high <= 2 * 104Problem 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.
This approach involves checking every possible pair (i, j) strictly where i < j, calculating their XOR, and checking if the result lies within the given range [low, high].
This C solution iterates through each combination of pairs, computes the XOR, and checks if it lies within the range [low, high]. If it does, it increments the count. Finally, it returns the count of such nice pairs.
Time Complexity: O(n^2), where n is the number of elements in the array, since we iterate over all possible pairs. Space Complexity: O(1), as we are not using any extra space proportional to the input size.
This approach involves building a Trie where each path represents a binary number in the array. Using the properties of XOR, we can efficiently count nice pairs by traversing this Trie.
This C solution uses a Trie to efficiently count the number of pairs whose XOR falls within a given range. By storing each number in binary form, it reduces search complexity when checking potential XOR values against the limits. The method achieves this by using Trie nodes to traverse potential number paths.
Time Complexity: O(n * 15), where 15 is the number of bits required to represent numbers up to 20000. Space Complexity: O(n * 15).
For this kind of problem that counts the interval [low, high], we can consider converting it into counting [0, high] and [0, low - 1], and then subtracting the latter from the former to get the answer.
In this problem, we can count how many pairs of numbers have an XOR value less than high+1, and then count how many pairs of numbers have an XOR value less than low. The difference between these two counts is the number of pairs whose XOR value is in the interval [low, high].
Moreover, for array XOR counting problems, we can usually use a "0-1 Trie" to solve them.
The definition of the Trie node is as follows:
children[0] and children[1] represent the left and right child nodes of the current node, respectively;cnt represents the number of numbers ending with the current node.In the Trie, we also define the following two functions:
One function is insert(x), which inserts the number x into the Trie. This function inserts the number x into the "0-1 Trie" in the order of binary bits from high to low. If the current binary bit is 0, it is inserted into the left child node, otherwise, it is inserted into the right child node. Then the count value cnt of the node is increased by 1.
Another function is search(x, limit), which searches for the count of numbers in the Trie that have an XOR value with x less than limit. This function starts from the root node node of the Trie, traverses the binary bits of x from high to low, and denotes the current binary bit of x as v. If the current binary bit of limit is 1, we can directly add the count value cnt of the child node that has the same binary bit v as x to the answer, and then move the current node to the child node that has a different binary bit v from x, i.e., node = node.children[v ^ 1]. Continue to traverse the next bit. If the current binary bit of limit is 0, we can only move the current node to the child node that has the same binary bit v as x, i.e., node = node.children[v]. Continue to traverse the next bit. After traversing the binary bits of x, return the answer.
With the above two functions, we can solve this problem.
We traverse the array nums. For each number x, we first search in the Trie for the count of numbers that have an XOR value with x less than high+1, and then search in the Trie for the count of pairs that have an XOR value with x less than low, and add the difference between the two counts to the answer. Then insert x into the Trie. Continue to traverse the next number x until the array nums is traversed. Finally, return the answer.
The time complexity is O(n times log M), and the space complexity is O(n times log M). Here, n is the length of the array nums, and M is the maximum value in the array nums. In this problem, we directly take log M = 16.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), where n is the number of elements in the array, since we iterate over all possible pairs. Space Complexity: O(1), as we are not using any extra space proportional to the input size. |
| Optimized Bit-Operation Approach Using Trie | Time Complexity: O(n * 15), where 15 is the number of bits required to represent numbers up to 20000. Space Complexity: O(n * 15). |
| 0-1 Trie | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Enumeration | O(n²) | O(1) | Small arrays or when verifying correctness of the XOR condition |
| Bitwise Trie Range Counting | O(n · B) | O(n · B) | Large inputs where efficient pair counting is required; standard optimal interview solution |
Count Pairs With Xor In A Range | Leetcode 1803 • Pepcoding • 5,527 views views
Watch 9 more video solutions →Practice Count Pairs With XOR in a Range with our built-in code editor and test cases.
Practice on FleetCode