# Count Pairs With XOR in a Range
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-pairs-with-xor-in-a-range)
Canonical: https://scaleengineer.com/dsa/problems/count-pairs-with-xor-in-a-range
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Trie
**Companies:** [Vimeo](https://scaleengineer.com/companies/vimeo)
---
## Problem
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 * 104`
* `1 <= nums[i] <= 2 * 104`
* `1 <= low <= high <= 2 * 104`

# Approaches
## Brute Force Iteration
The most straightforward approach is to iterate through every possible pair of numbers in the array, calculate their XOR, and check if the result falls within the specified range `[low, high]`. We maintain a counter which is incremented for each such 'nice pair'.
**Time:** O(N^2), where N is the length of the `nums` array. This is because we have nested loops that result in checking every unique pair of elements. · **Space:** O(1), as it only uses a constant amount of extra space for loop variables and the counter.
**Pros:** Simple to understand and implement.; Requires no additional space, making it very memory-efficient.
**Cons:** The quadratic time complexity makes it too slow for the given constraints, leading to a 'Time Limit Exceeded' error on larger test cases.
### Explanation
This method involves a brute-force check of all possible pairs `(i, j)` with `0 <= i < j < nums.length`. We use two nested loops to achieve this. The outer loop iterates from `i = 0` to `n-2` and the inner loop from `j = i + 1` to `n-1`, where `n` is the size of the `nums` array. Inside the inner loop, we compute the XOR of `nums[i]` and `nums[j]`. If this XOR value is greater than or equal to `low` and less than or equal to `high`, we increment our pair counter. While simple, this approach is inefficient for large arrays.

```java
class Solution {
    public int countPairs(int[] nums, int low, int high) {
        int n = nums.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int xorValue = nums[i] ^ nums[j];
                if (xorValue >= low && xorValue <= high) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use a nested loop to iterate through all unique pairs of indices `(i, j)` where `i < j`.
- For each pair, calculate the XOR value: `xorValue = nums[i] ^ nums[j]`.
- Check if the `xorValue` is within the range `[low, high]`.
- If `low <= xorValue <= high`, increment the `count`.
- After iterating through all pairs, return the final `count`.

## Optimized Approach using Trie
A much more efficient solution can be achieved using a Trie (prefix tree) and the principle of inclusion-exclusion. The number of pairs with XOR in the range `[low, high]` is equal to `(number of pairs with XOR <= high) - (number of pairs with XOR < low)`. This can be rewritten as `(number of pairs with XOR < high + 1) - (number of pairs with XOR < low)`. We can then focus on creating an efficient function, `countPairsSmallerThan(K)`, that leverages a Trie to count pairs with an XOR value less than `K`.
**Time:** O(N * B), where N is the length of `nums` and B is the number of bits in the numbers. For each of the N numbers, we perform a Trie query and insertion, both of which take O(B) time. Since B is a small constant (around 15), the complexity is effectively linear. · **Space:** O(N * B), where N is the number of elements and B is the number of bits used to represent the numbers (here, B is constant, ~15). The space is for the Trie, which can have up to N * B nodes in the worst case.
**Pros:** Highly efficient with a time complexity linear to the input size and number of bits.; A standard and powerful technique for solving problems involving XOR and ranges.
**Cons:** More complex to understand and implement compared to the brute-force approach.; Requires additional space to store the Trie data structure.
### Explanation
To implement `countPairsSmallerThan(K)`, we process each number in the `nums` array one by one. For each number `num`, we query a Trie to find how many numbers `x` inserted previously satisfy `x ^ num < K`. After the query, we insert `num` into the Trie for subsequent queries.

The Trie stores numbers in their binary form. Each node has two children (for bits 0 and 1) and a counter for the number of elements passing through it. The maximum value in the input is less than `2^15`, so we can use a fixed bit length of 15 (bits 14 down to 0).

The query function `countSmaller(num, K)` works by traversing the Trie from the most significant bit (MSB). At each bit `i`, it considers the `i`-th bit of `num` (`numBit`) and `K` (`kBit`):
- If `kBit` is 1: This means the `i`-th bit of the XOR result can be 0 to make the total value smaller than `K`. We find the path for `x` that makes the XOR bit 0 (`x_bit == numBit`) and add the count of all numbers in that subtree to our result. We then continue the traversal down the other path (where XOR bit is 1) to find pairs where the XOR prefix matches `K`'s prefix.
- If `kBit` is 0: The `i`-th bit of the XOR result must be 0. We must follow the path that makes it so (`x_bit == numBit`).

By applying this logic, we can efficiently count the pairs and solve the problem within the time limits.

```java
class Solution {
    class TrieNode {
        TrieNode[] children = new TrieNode[2];
        int count = 0;
    }

    private final int MAX_BIT = 14; // Constraints: nums[i], high < 2 * 10^4 < 2^15

    private void insert(TrieNode root, int num) {
        TrieNode curr = root;
        for (int i = MAX_BIT; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (curr.children[bit] == null) {
                curr.children[bit] = new TrieNode();
            }
            curr = curr.children[bit];
            curr.count++;
        }
    }

    // Counts numbers 'x' in the trie such that x ^ num < K
    private int countSmaller(TrieNode root, int num, int K) {
        TrieNode curr = root;
        int count = 0;
        for (int i = MAX_BIT; i >= 0 && curr != null; i--) {
            int numBit = (num >> i) & 1;
            int kBit = (K >> i) & 1;

            if (kBit == 1) {
                // If k_bit is 1, we can make xor_bit 0.
                // To make xor_bit 0, x_bit must be numBit.
                // All numbers in this path's subtree will result in a smaller XOR value.
                if (curr.children[numBit] != null) {
                    count += curr.children[numBit].count;
                }
                // We must continue down the path where xor_bit is 1 to match K's prefix.
                // To make xor_bit 1, x_bit must be 1 - numBit.
                curr = curr.children[1 - numBit];
            } else { // kBit == 0
                // To not exceed K, xor_bit must be 0.
                // To make xor_bit 0, x_bit must be numBit.
                curr = curr.children[numBit];
            }
        }
        return count;
    }

    // Counts pairs with XOR < K
    private int countPairsSmallerThanK(int[] nums, int K) {
        TrieNode root = new TrieNode();
        int totalCount = 0;
        for (int num : nums) {
            totalCount += countSmaller(root, num, K);
            insert(root, num);
        }
        return totalCount;
    }

    public int countPairs(int[] nums, int low, int high) {
        // Count pairs with XOR in [low, high] is (count < high + 1) - (count < low)
        return countPairsSmallerThanK(nums, high + 1) - countPairsSmallerThanK(nums, low);
    }
}
```
### Algorithm
- The main problem of counting pairs in a range `[low, high]` is transformed into two subproblems: `countPairsSmallerThan(high + 1) - countPairsSmallerThan(low)`.
- Implement a function `countPairsSmallerThan(K)` that counts pairs with XOR value strictly less than `K`.
- This function uses a Trie to store the binary representations of numbers processed so far.
- Iterate through each `num` in the `nums` array:
  - Query the Trie to count how many existing numbers `x` result in `x ^ num < K`.
  - Add this count to a running total.
  - Insert the current `num` into the Trie.
- The Trie query function traverses the bits of `num` and `K` from most significant to least significant to efficiently count the valid pairs.

# Solutions
### Java

```java
class Trie { private Trie [] children = new Trie [ 2 ]; private int cnt ; public void insert ( int x ) { Trie node = this ; for ( int i = 15 ; i >= 0 ; -- i ) { int v = ( x >> i ) & 1 ; if ( node . children [ v ] == null ) { node . children [ v ] = new Trie (); } node = node . children [ v ]; ++ node . cnt ; } } public int search ( int x , int limit ) { Trie node = this ; int ans = 0 ; for ( int i = 15 ; i >= 0 && node != null ; -- i ) { int v = ( x >> i ) & 1 ; if ((( limit >> i ) & 1 ) == 1 ) { if ( node . children [ v ] != null ) { ans += node . children [ v ]. cnt ; } node = node . children [ v ^ 1 ]; } else { node = node . children [ v ]; } } return ans ; } } class Solution { public int countPairs ( int [] nums , int low , int high ) { Trie trie = new Trie (); int ans = 0 ; for ( int x : nums ) { ans += trie . search ( x , high + 1 ) - trie . search ( x , low ); trie . insert ( x ); } return ans ; } }
```

### CPP

```cpp
class Trie { public: Trie () : children ( 2 ) , cnt ( 0 ) {} void insert ( int x ) { Trie * node = this ; for ( int i = 15 ; ~ i ; -- i ) { int v = x >> i & 1 ; if ( ! node -> children [ v ]) { node -> children [ v ] = new Trie (); } node = node -> children [ v ]; ++ node -> cnt ; } } int search ( int x , int limit ) { Trie * node = this ; int ans = 0 ; for ( int i = 15 ; ~ i && node ; -- i ) { int 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 ; } private: vector < Trie *> children ; int cnt ; }; class Solution { public: int countPairs ( vector < int >& nums , int low , int high ) { Trie * tree = new Trie (); int ans = 0 ; for ( int & x : nums ) { ans += tree -> search ( x , high + 1 ) - tree -> search ( x , low ); tree -> insert ( x ); } return ans ; } };
```

### Python

```python
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
```