Beautiful Xor Pairs

Hard
0/120
Average time to solve is 45m
profile
Contributed by
10 upvotes
Asked in company
IBM

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’.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
1 1 2
1
4 6 8
3 4 5 2
Sample Output 1:
0
4
Explanation of sample input 1:
In the first test case, there is only one integer in ‘ARR’ so no pair is possible.

In the second test case, There are 6 pairs as follow -:
1. (0, 1):  ‘ARR[0]’ XOR ‘ARR[1]’ = 3 XOR 4 = 7
2. (0, 2):  ‘ARR[0]’ XOR ‘ARR[2]’ = 3 XOR 5 = 6
3. (0, 3):  ‘ARR[0]’ XOR ‘ARR[3]’ = 3 XOR 2 = 1
4. (1, 2):  ‘ARR[1]’ XOR ‘ARR[2]’ = 4 XOR 5 = 1
5. (1, 3):  ‘ARR[1]’ XOR ‘ARR[3]’ = 4 XOR 2 = 6
6. (2, 3):  ‘ARR[2]’ XOR ‘ARR[3]’ = 5 XOR 2 = 7
Clearly, there are 4 beautiful pairs i.e (0, 1), (0, 2), (1, 3) and (2, 3)
Sample Input 2:
2
4 2 6
1 4 2 7
5 5 14
9 8 4 2 1
Sample Output 2:
6
8
Hint

Find out the xor of each pair.

Approaches (2)
Brute Force

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:

  1. Initialize an integer variable ‘COUNTER’: = 0.
  2. 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.
  3. Return ‘COUNTER’.
Time Complexity

O(N ^ 2), where 'N' is the size of ‘ARR’.

 

There are O(N ^ 2) pairs of indexes in ‘ARR’ and it takes O(1) time to find xor of each of them and check whether it is in the range [LOW, HIGH] or not. Thus, the overall time complexity will be O(N^2). 

Space Complexity

O(1)

 

We are using constant extra space here.

Code Solution
(100% EXP penalty)
Beautiful Xor Pairs
Full screen
Console