1803. Count Pairs With XOR in a Range

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

Example: 2

Input: nums = [9,8,4,2,1], low = 5, high = 14

Output: 8

Constraints:

• 1 <= nums.length <= 2 * 10 ^ 4
• 1 <= nums[i] <= 2 * 10 ^ 4
• 1 <= low <= high <= 2 * 10 ^ 4

Data structure required for solving this problem:

• To solve this problem we need a data structure called trie.

Steps required to solve the problem:

• First we will add i - 1 elements into the trie(also while adding an element, we have to maintain the count of branches that have common prefixes so that our querying will be efficient) and then check if ith element in the array will make pairs with the elements added in the trie whose xor value is less than or equal to K.
• By proceeding in this manner we will get the number of pairs we can calculate number of pairs giving xor less than or equal to K. Let's call the function used to get this count be called query(K)
• So, for getting number of pairs between low and high, we will do query(high) - query(low - 1) and that will be our answer.

Getting number of pairs having xor values less than or equal to K:

• This is the most trickiest part of this problem.
• Let's take the first example, where array is [1, 4, 2, 7], low = 2 and high = 6. And let's say you are at index 2 (i.e element 1 and 4 are added into the trie).
• The thing you have to do here is to see that, whether the element in the trie generates an xor value less than or equal to K when xored with the current element (i.e in our case 2).
• To do this traverse down the trie one bit at a time.
• Then check the value of bit in current position of our element and K.
• Then there comes 4 cases... we will handle them separately.

Case I (current bit of element is 0 and current bit of K is 0):

• When both bits in current position are 0, you can only choose the branch that comes by taking 0. This is because if you take branch having 1 value, then, this 1 when xored with current bit of our element (i.e 0) will yield 1, which in turn will make the number bigger than K.
• Note that you only take the branch which appears by taking 0, but do not add it's count value because we don't yet know whether this number will turn out to be bigger than K or not. However, if its the last bit of your element you can add this to your answer because it will give same xor equal K.
• Also, we cannot take the branch that appears by taking 1, because it will give always xor value bigger than K.

Case II (current bit of element is 0 and current bit of K is 1):

• In this case, you are free to take any branch that comes after taking 0. This is because when you xor this 0 with our current element's bit(i.e 0), our answer will always be smaller than K (because K's current bit is 1). So add the count of branches that will appear after taking 0 to the final answer.
• And as for the branch which appears after taking 1, we can only take that branch but not add its count to the answer, as we don't know whether the number will turn out to be bigger than K or not. However, if its the last bit of your element you can add this to your answer because it will give same xor equal K.

Case III (current bit of element is 1 and current bit of K is 0):

• In this case, we cannot take the branches that appear after taking 0 in our final answer. This is because, when this 0 is xored with our current element's bit (i.e 1) will yield 1, which will be greater than K.
• But we can go to the branch that comes by taking 1, but cannot add their count into the final answer because we don't yet know whether this number will turn out to be bigger than K or not. However, if its the last bit of your element you can add this to your answer because it will give same xor equal K.

Case IV (current bit of element is 1 and current bit of K is 1):

• In this case, you are free to take any branch that comes after taking 1. This is because when you xor this 1 with our current element's bit(i.e 1), our answer will always be smaller than K (because K's current bit is 1 and xored value is 0). So add the count of branches that will appear after taking 1 to the final answer.
• And as for the branch which appears after taking 0, we can only take that branch but not add its count to the answer, as we don't know whether the number will turn out to be bigger than K or not. However, if its the last bit of your element you can add this to your answer because it will give same xor equal K.

Full Code (Java): class Solution { int BITS_LIMIT = 16; public int countPairs(int[] nums, int low, int high) { Trie trie = new Trie(); trie.add(getString(nums[0])); int temp = 0; for(int i = 1; i < nums.length; i++) { temp += trie.query(getString(nums[i]), getString(high)); temp -= trie.query(getString(nums[i]), getString(low - 1)); trie.add(getString(nums[i])); } return temp; } // get string of number converted to binary String getString(int num) { String ret = Integer.toBinaryString(num); while(ret.length() < BITS_LIMIT) { ret = "0" + ret; } return ret; } // trie code class Trie { Node root; public Trie() { root = new Node(); } void add(String s) { Node trav = root; for(int i = 0; i < s.length(); i++) { char c = s.charAt(i); if(!trav.map.containsKey(c)) { trav.map.put(c, new Node()); } trav = trav.map.get(c); trav.count++; } } int query(String n, String limit) { int ans = 0; Node trav = root; for(int i = 0; i < n.length(); i++) { char N = n.charAt(i); char L = limit.charAt(i); if(trav == null) break; // case handling as explained above if(N == '0' && L == '0') { trav = trav.map.getOrDefault('0', null); if(trav != null && i == n.length() - 1) { ans += trav.count; } } else if(N == '0' && L == '1') { Node left = trav.map.getOrDefault('0', null); if(left != null) { ans += left.count; } trav = trav.map.getOrDefault('1', null); if(trav != null && i == n.length() - 1) { ans += trav.count; } } else if(N == '1' && L == '0') { trav = trav.map.getOrDefault('1', null); if(trav != null && i == n.length() - 1) { ans += trav.count; } } else { Node right = trav.map.getOrDefault('1', null); if(right != null) { ans += right.count; } trav = trav.map.getOrDefault('0', null); if(trav != null && i == n.length() - 1) { ans += trav.count; } } } return ans; } class Node { int count; HashMap<Character, Node> map; public Node() { count = 0; map = new HashMap<>(); } } } }