#1803

Hard

LeetCode Problem Workspace

Count Pairs With XOR in a Range

Count all pairs in an array whose XOR falls within a given range using efficient bit manipulation techniques and a trie structure.

array bit manipulation trie

Problem Statement

Given a 0-indexed integer array nums and two integers low and high, return the number of nice pairs. A nice pair is defined as a pair of indices (i, j) where 0 ≤ i < j < nums.length and the XOR of nums[i] and nums[j] lies within the range [low, high].

For example, given nums = [1,4,2,7] with low = 2 and high = 6, the six nice pairs are (0,1), (0,2), (0,3), (1,2), (1,3), and (2,3) as their XOR results all fall between 2 and 6. You must count all such pairs efficiently, leveraging the array plus bit manipulation pattern.

Examples

Example 1

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

Output: 6

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

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 * 104
1 <= nums[i] <= 2 * 104
1 <= low <= high <= 2 * 104

Solution Approach

Use a Trie for Bitwise Prefixes

Build a binary trie storing the binary representation of numbers seen so far. For each number, traverse the trie to count how many previous numbers generate an XOR within the target range. This approach reduces the need for O(n^2) brute-force comparisons.

Count XOR ≤ K Efficiently

Implement a helper to compute the number of pairs with XOR ≤ a given K by navigating the trie bit by bit. For the main solution, count pairs ≤ high and subtract pairs < low to get the number of valid nice pairs in the range [low, high].

Iterate Through the Array

Process each element sequentially, updating the trie and counting pairs with the XOR bounds. Careful bitwise handling ensures accurate counts and handles the array length constraints efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * log M), where M is the maximum number representable in nums (up to 2*10^4), since each trie operation traverses at most log M bits. Space complexity is O(n * log M) for storing the trie nodes corresponding to prefix XORs.

What Interviewers Usually Probe

Notice the problem can be reduced to counting pairs with XOR ≤ K.
Trie usage hints at bit manipulation optimization over brute-force pair checks.
Be careful with edge cases where low equals high or duplicates exist in the array.

Common Pitfalls or Variants

Common pitfalls

Attempting O(n^2) brute-force pair enumeration results in TLE for large arrays.
Failing to subtract pairs < low from pairs ≤ high leads to incorrect counts.
Not handling bits properly in the trie, especially for leading zeros, can cause undercounting.

Follow-up variants

Count pairs with XOR exactly equal to K instead of a range.
Find the maximum XOR obtainable from any pair in the array.
Count triplets where XOR of three numbers lies in a given range.

FAQ

What is a nice pair in 'Count Pairs With XOR in a Range'?

A nice pair is any pair of indices (i, j) where 0 ≤ i < j < nums.length and the XOR of nums[i] and nums[j] falls between the given low and high values.

Why use a trie instead of brute-force?

A trie allows bitwise traversal to count XOR pairs efficiently, reducing the O(n^2) brute-force complexity to O(n * log M).

How does the XOR ≤ K trick help?

By counting pairs with XOR ≤ high and subtracting pairs with XOR < low, we directly compute the number of pairs within the range without checking all combinations.

Can duplicates in nums affect the count?

Yes, duplicates are counted separately per index pair, and the trie approach correctly handles them in the XOR computation.

Is this problem only about bit manipulation?

While bit manipulation is central, the key pattern combines arrays and trie traversal to efficiently count range-limited XOR pairs.

terminal

Solution

Solution 1: 0-1 Trie

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

class Trie:
    def __init__(self):
        self.children = [None] * 2
        self.cnt = 0

    def insert(self, x):
        node = self
        for i in range(15, -1, -1):
            v = x >> i & 1
            if node.children[v] is None:
                node.children[v] = Trie()
            node = node.children[v]
            node.cnt += 1

    def search(self, x, limit):
        node = self
        ans = 0
        for i in range(15, -1, -1):
            if node is None:
                return ans
            v = x >> i & 1
            if limit >> i & 1:
                if node.children[v]:
                    ans += node.children[v].cnt
                node = node.children[v ^ 1]
            else:
                node = node.children[v]
        return ans


class Solution:
    def countPairs(self, nums: List[int], low: int, high: int) -> int:
        ans = 0
        tree = Trie()
        for x in nums:
            ans += tree.search(x, high + 1) - tree.search(x, low)
            tree.insert(x)
        return ans

Continue Practicing

#1707 maximum xor with an element from array #1938 maximum genetic difference query #1178 number of valid words for each puzzle