Subset OR

Posted: 31 Jul, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
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
Approach 1


 

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’).

Try Problem