Last Updated: 4 Apr, 2021

Beautiful Xor Pairs

Hard

Asked in company

Solve now

Problem statement

Ninja has an array ‘ARR’ consisting of ‘N’ positive integers. He also has two positive integers ‘LOW’, ‘HIGH’ such that ‘HIGH’ >= ‘LOW’.

According to Ninja, a pair of integers (i, j) is considered beautiful if 0 <= i < j < ‘N’ and ‘LOW’ <= (‘ARR[i]’ XOR ‘ARR[j]’) <= ‘HIGH’.

Ninja wants to count beautiful pairs in ‘ARR’. Find and return the number of beautiful pairs in ‘ARR’ on behalf of Ninja.

Note:

1. Consider 0 based indexing in ‘ARR’.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain three space-separated integers ‘N’, ‘LOW’, and ‘HIGH’ respectively representing the size of ‘ARR’ and the two integers that Ninja have between which the xor of every beautiful pair must lie.

The second line of each test case will contain ‘N’ space-separated integers representing array/list ‘ARR’.

Output Format:

For each test case, print a single integer representing the number of beautiful pairs in ‘ARR’.

Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of.

Constraints:

1 <= T <= 50
1 <= N <= 10000
1 <= ARR[i] <= 20000
1 <= LOW <= HIGH <= 20000


Where ‘T’ is the number of test cases, 'N' is the size of ‘ARR’, and ‘LOW’, ‘HIGH’  are the integers that Ninja have, ‘ARR[i]’ is the ‘i-th’ element of arraylist ‘ARR’ 

Time limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea is to initialize an integer variable ‘COUNTER’: = 0 and one by one find the XOR of each valid pair of integers in ‘ARR’. If for a pair xor is in the range [‘LOW’, ‘HIGH’] then increment ‘COUNTER’ by 1.

The steps are as follows:

Initialize an integer variable ‘COUNTER’: = 0.
Run a loop where ‘i’ ranges from 0 to ‘N’-1 and for each ‘i’ do the following -:
1. Run a loop where ‘j’ ranges from ‘i’+1 to ‘N’-1 and do the following -:
  1. If ‘ARR[i]’ XOR ‘ARR[j]’ >= ‘LOW’ and ‘ARR[i]’ XOR ‘ARR[j]’ <= ‘HIGH’ then increment ‘COUNTER’ by 1.
Return ‘COUNTER’.

Solve now

02 Approach

The basic idea is to use trie to solve this problem. Trie here is basically a rooted binary tree where each edge is either labelled by 0 or 1 and the node will have a value equal to the number of elements in the trie having a prefix given by path from the root to that node.

We iterate over the given array ‘ARR’ and for each integer in ‘ARR’ count the number of elements present in the Trie whose bitwise XOR with the current integer is in the range [LOW, HIGH], and then insert this integer in the trie by converting it in 16-bit binary format.

Let F(X) be the number of elements in the trie whose bitwise XOR with a current integer is less than ‘X’, then we need to find F(HIGH+1) - F(LOW).

We can find F(X) as follow -:

Initialize an integer variable ‘COUNT’: = 0.
Keep a pointer ‘p’ at the root of the trie.
Run a loop where ‘i’ ranges from 15 to 0 and do the following -:
1. Let ‘CURBIT’ be the XOR of the ‘i-th’ bit of ‘X’ with ‘i-th’ bit of the current integer. Clearly ‘CURBIT’ is either 0 or 1.
2. If the ‘i-th’ bit of ‘X’ is 1, then add the value of the node followed by an edge labelled with 1 - ’CURBIT’ from the pointer ‘p’ in ‘COUNT’. (If exists)
3. Move pointer ‘p’ to the node followed by an edge labelled with ‘CURBIT’. If it doesn’t exist then break the loop.
Return ‘COUNT’.

Now the complete problem can be solved by using this algorithm of finding F(X) as follows -:

Initialize an integer variable ‘COUNTER’: = 0.
Create an empty trie.
Run a loop where ‘i’ ranges from 0 to ‘N’-1 and do the following -:
1. Do COUNTER: = COUNTER + F(HIGH+1) - F(LOW).
2. Insert ARR[i] in the trie by converting it into 16-bit binary format.
Return ‘COUNTER’.

Solve now