Count Pairs With XOR in a Range

Hard

#1649Time: 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.1 company

Patterns

Bit Manipulation

Data structures

Array Trie

Companies

Vimeo

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

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'.

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.

Walkthrough

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.

1class Solution {2    public int countPairs(int[] nums, int low, int high) {3        int n = nums.length;4        int count = 0;5        for (int i = 0; i < n; i++) {6            for (int j = i + 1; j < n; j++) {7                int xorValue = nums[i] ^ nums[j];8                if (xorValue >= low && xorValue <= high) {9                    count++;10                }11            }12        }13        return count;14    }15}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    class TrieNode {3        TrieNode[] children = new TrieNode[2];4        int count = 0;5    }6 7    private final int MAX_BIT = 14; // Constraints: nums[i], high < 2 * 10^4 < 2^158 9    private void insert(TrieNode root, int num) {10        TrieNode curr = root;11        for (int i = MAX_BIT; i >= 0; i--) {12            int bit = (num >> i) & 1;13            if (curr.children[bit] == null) {14                curr.children[bit] = new TrieNode();15            }16            curr = curr.children[bit];17            curr.count++;18        }19    }20 21    // Counts numbers 'x' in the trie such that x ^ num < K22    private int countSmaller(TrieNode root, int num, int K) {23        TrieNode curr = root;24        int count = 0;25        for (int i = MAX_BIT; i >= 0 && curr != null; i--) {26            int numBit = (num >> i) & 1;27            int kBit = (K >> i) & 1;28 29            if (kBit == 1) {30                // If k_bit is 1, we can make xor_bit 0.31                // To make xor_bit 0, x_bit must be numBit.32                // All numbers in this path's subtree will result in a smaller XOR value.33                if (curr.children[numBit] != null) {34                    count += curr.children[numBit].count;35                }36                // We must continue down the path where xor_bit is 1 to match K's prefix.37                // To make xor_bit 1, x_bit must be 1 - numBit.38                curr = curr.children[1 - numBit];39            } else { // kBit == 040                // To not exceed K, xor_bit must be 0.41                // To make xor_bit 0, x_bit must be numBit.42                curr = curr.children[numBit];43            }44        }45        return count;46    }47 48    // Counts pairs with XOR < K49    private int countPairsSmallerThanK(int[] nums, int K) {50        TrieNode root = new TrieNode();51        int totalCount = 0;52        for (int num : nums) {53            totalCount += countSmaller(root, num, K);54            insert(root, num);55        }56        return totalCount;57    }58 59    public int countPairs(int[] nums, int low, int high) {60        // Count pairs with XOR in [low, high] is (count < high + 1) - (count < low)61        return countPairsSmallerThanK(nums, high + 1) - countPairsSmallerThanK(nums, low);62    }63}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ; } };

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem