Count OR Pairs

Easy
0/40
Average time to solve is 10m
profile
Contributed by
4 upvotes
Asked in company
Sprinklr

Problem statement

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)}
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4
2 15 1 10
3
3
18 6 11
7
Sample Output 2 :
5
3
Explanation For Sample Input 1 :
For the first test case, possible pairs with their OR value are :
(2,15) : 2 OR 15 = 15
(2,1) : 2 OR 1 = 3
(2,10) : 2 OR 10 = 10
(15,1) :15 OR 1 = 15
(15,10) : 15 OR 10 = 15
(1,10) : 1 OR 10 = 11
Therefore, the total number of pairs having OR values greater than 3 are 5.

For the second test case, pairs with their OR value greater than 7 are : (18,6), (18,11), (6,11).
Therefore, the total number of pairs having OR value greater than 7 are 3.
Sample Input 2 :
2
3
1 2 3
1
5
2 5 6 10 9
10
Sample Output 2 :
2
0
Explanation For Sample Input 2 :
For the first test case, pairs with their OR value are : (1, 3), (2, 3).
Therefore, the total number of pairs having OR values greater than 2 are 3.

For the second test case pairs with their OR value greater than 10 are : 0
Therefore, the total number of pairs having OR values greater than 10 are 0.
Hint

Find OR value for all the pairs of the array ‘ARR’.

Approaches (2)
Brute Force

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 :

 

  1. Create a variable (say, ‘COUNT’) to store the number of pairs.
  2. 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.
  3. Finally, return ‘COUNT’.
Time Complexity

O(N^2), where ‘N’ is the size of the given array.

 

Total number of pairs in an array of size ‘N’ will be N*(N-1)/2. We are checking OR value for every pair. Therefore, the overall time complexity will be O(N^2).

Space Complexity

O(1)
 

Since, we are not using any extra space to find the number of pairs. Therefore, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Count OR Pairs
Full screen
Console