Last Updated: 8 Dec, 2020
Count OR Pairs
Easy
Asked in company
Given an array ‘ARR’ of ‘N’ integers. Find the number of pairs with OR value greater than ‘K’ in a given array ‘ARR’.
Note :
Here OR represents the bitwise operator | which returns 1 if any of the two bits is 1.
‘K’ is of the form 2^p -1 where ‘p’ is any positive integer.
Example :
‘ARR’ : {1, 2, 3} and ‘K’ : 2
Then the number of pairs with OR value greater than ‘K’ are : 2 i.e. {(2, 3), (1, 3)}
Input Format :
The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow :
The first line in each test case contains a single integer ‘N’ representing the size of the array ‘ARR’.
The second line in each test case contains ‘N’ integers separated by space representing elements of the array.
The third line in each test case contains a single integer ‘K’.
Output Format :
For each test case, print the total number of pairs with OR value greater than ‘K’ in a given array ‘ARR’.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^4
1<= ARR[i] <= 5*10^4
1 <= K <= 2^31 - 1
Time Limit : 1 sec
Approaches
The simplest approach is to traverse the ‘ARR’ and generate all possible pairs and for each pair, check if the bitwise OR of the pair is greater than ‘K’ or not.
Here is the algorithm :
- Create a variable (say, ‘COUNT’) to store the number of pairs.
- Run a loop from 0 to ‘N’ (say, iterator = ‘i’)
- Run a nested loop from ‘i’ + 1 to ‘N’ (say, iterator = ‘j’)
- Check if OR value of ‘ARR[i]’ and ‘ARR[j]’ is greater than ‘K’ :
- Increment ‘COUNT’ with 1.
- Check if OR value of ‘ARR[i]’ and ‘ARR[j]’ is greater than ‘K’ :
- Run a nested loop from ‘i’ + 1 to ‘N’ (say, iterator = ‘j’)
- Finally, return ‘COUNT’.
The approach is to find the number of elements greater than ‘K’. Elements greater than ‘K’ can form the pairs with every other element of the ‘ARR’. Because if a number is greater than ‘K’ then the OR value of it with any other number will also be greater than ‘K’.
Let’s take an example :
Let the array be ARR[] : {15, 2, 4}
Let ‘K’ be : 7
Bit representation of ‘K’ is : 0111
Bit representation of ‘ARR[0]’ i.e. 15 is : 1111
Bit representation of ‘ARR[1]’ i.e. 2 is : 0010
OR value of ‘ARR[0]’ and ‘ARR[1]’ : 15 | 2 = 15
While the numbers smaller than ‘K’ will not form pairs with each other. In the above example {4,2} will not form the pair (OR value of 4 and 2 is 6).
Here is the algorithm:
- Create a variable (say, ‘COUNT’) to store the number of pairs and initialise it with 0
- Create a variable (say, ‘countK’) to store the elements greater than K and initialise it with 0.
- Run a loop from 0 to ‘N’ (say, iterator = ‘i’)
- Check if ‘ARR[i]’ is greater than ‘K’ :
- Increment ‘COUNT_K’ with 1
- Increment ‘COUNT’ with ( ‘N’ - ‘COUNT_K’) ( We can form ‘N’ pairs with a number greater than ‘K’. But we need to subtract ‘COUNT_K’ each time while adding so the pairs are not repeated).
- Finally, return ‘COUNT’.