Subset OR

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
95 upvotes
Asked in company
Google inc

Problem statement

You are given an array/list ‘ARR’ of ‘N’ positive integers’. Your task is to find out the size of the smallest subset with the maximum OR possible. That means that among all subsets that have OR of its elements maximum, you need to report the size of the smallest such subset.

For Example : 
Input : arr[] = {5, 1, 3, 4, 2}   
Output : 2
7 is the maximum value possible of OR, 
5|2 = 7 and 5|3 = 7
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases.Then ‘T’ test cases follow.

The first line of each test case contains the integer ‘N’ representing the size of the input ‘ARR’.

The next line of each test case contains ‘N’ single space-separated integers that represent the elements of the ‘ARR’.
Output Format : 
For each test case, return an integer denoting the size of the smallest subset with maximum possible OR.
Output for each test case will be printed in a separate line.
Note: 
You don’t need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= N <= 10^4
0 <= ARR[i] <= 10^3

Time Limit: 1 sec
Sample Input 1 :
1
6
2 6 2 8 4 5
Sample Output 1 :
3
Explanation Of Sample Output 1 :
15 is the maximum value of OR and set elements are 8, 6, and 5.
Sample Input 2 :
1
5
5 1 3 4 2
Sample Output 2 :
 2
Hint

Can you find every possible subset of ‘ARR’ and check if its OR is equal to maxmum?

Approaches (3)
Recursion


 

The maximum possible OR of any subset is the OR of the whole array. So let the OR of the whole array be equal to ‘K’.

The idea is to generate all possible subsets and check if any of them OR up to ‘K’. This can be done through recursion.

Here is the algorithm:

subsetOR(N , ARR):

  1. Initialize the variable ‘K’ = OR of the complete array.
  2. Initialize integer variable ‘ANS’ = ‘helper(ARR, N, K, 0)’. Here ‘helper’ is the recursive function that returns the size of a minimal subset.
  3. Return ANS.


 

helper(ARR, N, K, curr):

  1. Base case: If ‘N’ is less than or equal to 0:
    • If ‘K’ is equal to curr:
      • Return 1.
    • Else:
      • Return inf.
  2. Initialize integer variable ‘X’ = ‘helper(ARR, N-1, K, curr)’. Here, ‘ARR[N-1]’ is not included in the OR.
  3. Initialize integer variable ‘Y’ = ‘1 + helper(ARR, N-1, K curr | ARR[N - 1]])’. Here, ‘ARR[N-1]’ is included in the sum.

Return min(‘X’, ‘Y’).

Time Complexity

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


 

Since from each recursive call, we make 2 new recursive calls. Hence the time complexity is O(2^N).

Space Complexity

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

 

O(N) space is used in recursion for stack space at a time. Hence the space complexity is O(N).

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