Range XOR Pairs
Solve a hard-level problem of finding the count of pairs with their XOR value in a range using tries.
Problem statement
Given an integer array nums and a range in the form of [low, high], return the count of pairs(i, j) such that 0 <= i < j < nums.size and low <= (nums[i] XOR nums[j]) <= high.
Example 1
Sample input
nums: [1,2,3,4]low = 2high = 5
Sample output
3
Explanation
All valid pairs (i, j) are as follows:
nums[0]XORnums[1]= 3nums[0]XORnums[2]= 2nums[0]XORnums[3]= 5nums[1]XORnums[2]= 1nums[1]XORnums[3]= 6nums[2]XORnums[3]= 7
Example 2
Sample input:
nums: [9,8,4,2,1]low = 5high = 14
Sample output:
8
Explanation:
All valid pairs (i, j) are as follows:
nums[0]XORnums[2]= 13nums[0]XORnums[3]= 11nums[0]XORnums[4]= 8nums[1]XORnums[2]= 12nums[1]XORnums[3]= 10nums[1]XORnums[4]= 9nums[2]XORnums[3]= 6nums[2]XORnums[4]= 5
Try it yourself
Try to solve the problem yourself before reading the solution.
#include <iostream>#include <vector>using namespace std;int countPairsInRange(vector<int> nums, int low, int high) {// your code goes herereturn -1;}
Intuition
If we can find a way to count the number of pairs for which XOR is less than a specific value, we can utilize that method to calculate the two values.
Let (A) = The number of pairs with XOR value less than high+1.
Let (B) = The number of pairs with XOR value less than low.
Subtracting (B) from (A) would provide the count of pairs with XOR values in the low-to-high range.
countOfPairsInRange(low, high) = countOfPairsLessThan(high+1) - countOfPairsLessThan(low)
Therefore, we need to find a way to count the number of pairs with XOR values less than some limit.
Algorithm
Below is the summary of the algorithm adopted for finding range XOR pairs.
Step 1: Insert integers in the trie
Traverse the array and insert the binary representations of the integers in the trie. While inserting, check how many numbers that are already present in the trie will have an XOR value with the current number less than some specified limit. Thus, we can calculate the value of (A) and (B) (defined above) to find the final answer. Below is the pseudocode to do this:
// intialize a new trieTrie trie = new Trie()// intialize a ans to zeroans = 0for element in array {// calculate (A) and (B)ans += trie.countXorLessThan(element, high+1)ans -= trie.countXorLessThan(element, low)trie.insert(element)}return ans
Step 2: Calculate XOR less than limit
But how can we calculate the count of numbers with XOR values less than the limit? This can be done by traversing the trie and taking the path where taking XOR with the current element bit will result in a value equal to the limit. Count all the numbers smaller than the limit, ignore all the ones that are bigger than the limit, and add it to the answer.
Step 3: Calculate XOR pairs
How can we calculate the number of pairs? One possible solution is to count how many pairs an integer can create with numbers already in the trie before inserting the number in the trie. But for that to be possible, we need some extra information to be stored with each trie node. A count parameter should be associated with each trie node, determining the count of integers present under that node. This will help us in finding out the number of pairs easily.
For inserting an integer in the trie, we need to compare all bits of the limit integer and the integer inserted in the trie, going from the most significant to the least significant bit. For each comparison, we need to define an action around the path to be taken while traversing down the trie. So, based on the problem requirements, this is how we traverse down in the trie, comparing bits of the limit value and the ...