Subset OR
Last Updated: 31 Jul, 2021
Difficulty: Moderate
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):
- Initialize the variable ‘K’ = OR of the complete array.
- Initialize integer variable ‘ANS’ = ‘helper(ARR, N, K, 0)’. Here ‘helper’ is the recursive function that returns the size of a minimal subset.
- Return ANS.
helper(ARR, N, K, curr):
- Base case: If ‘N’ is less than or equal to 0:
- If ‘K’ is equal to curr:
- Return 1.
- Else:
- Return inf.
- If ‘K’ is equal to curr:
- Initialize integer variable ‘X’ = ‘helper(ARR, N-1, K, curr)’. Here, ‘ARR[N-1]’ is not included in the OR.
- 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’).
Approach 2
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’. Along with that, we will use memoization to store previously calculated results to avoid repetition and hence improving the time complexity.
Here is the algorithm:
subsetOR(N , ARR):
- Initialize the variable ‘K’ = OR of the complete array.
- Create 2D array/list ‘MEMO’ of size (‘N’+1) * (‘K’ + 1) i.e. ‘MEMO[N+1][K+1]’.
- Store -1 at all indices of ‘MEMO’. (This ‘MEMO’ array/list will be used to store the previously calculated results).
- Initialize integer variable ‘ANS’ = ‘helper(ARR, N, K, 0, MEMO)’. Here ‘helper’ is the recursive function that returns the required size.
- Return ANS.
helper(ARR, N, K, MEMO):
- Base case: If ‘N’ is less than or equal to 0:
- If ‘K’ is equal to curr:
- Return 0.
- Else:
- Return inf.
- If ‘K’ is equal to curr:
- If ‘MEMO[N][curr]’ is not equal to -1, i.e. value for this combination of ‘N’ and ‘curr’ is already calculated, then:
- Return ‘MEMO[N][curr]’.
- Initialize integer variable ‘X’ = ‘helper(ARR, N-1, K, curr)’. Here, ‘ARR[N-1]’ is not included in the OR.
- Initialize integer variable ‘Y’ = ‘1 + helper(ARR, N-1, K curr | ARR[N - 1]])’. Here, ‘ARR[N-1]’ is included in the sum.
- ‘MEMO[N][curr]’ = min(‘X’, ‘Y’).
- Return ‘MEMO[N][curr]’.
Approach 3
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 use dynamic programming to generate all the possible subsets and check if these subsets OR up to ‘K’.
Here is the algorithm:
- Create a boolean 2D array/list ‘DP’ of size (‘N+1’)*(‘K+1’) i.e. ‘DP[N+1][K+1]’. Here DP[i][j] stores the minimum size of the subset needed to get OR = j considering the first i indices.
- If ‘K’ is equal to 0, then the answer should be 0. Hence, run a loop from 0 to ‘N’ (say iterator = ‘i’):
- ‘DP[i][0]’ = 0.
- If ‘K’ is not zero but ‘ARR’ is empty then the answer should be ‘inf’. Hence, run a loop from 1 to ‘K’ (say iterator = ‘i’):
- ‘DP[0][i]’ = inf.
- To fill the ‘DP’ table, run a loop from 0 to ‘N - 1’ (say iterator = ‘i’):
- Run a loop from 0 to ‘K’ (say iterator = ‘j’):
- ‘DP[i + 1][j]’ = ‘DP[i][j]’.
- If ‘j | A[i]’ is smaller than equal to k‘’:
- ‘DP[i + 1][j | A[i]]’ = min(‘DP[i + 1][j | A[i]]’ , 1 + ‘DP[i][j] )’.
- Run a loop from 0 to ‘K’ (say iterator = ‘j’):
- Finally, return ‘DP[N][K]’.
