62

Subset OR

Difficulty: MEDIUM
Contributed By
Hardik Aggarwal
Avg. time to solve
20 min
Success Rate
80%

Problem Statement
Suggest Edit

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
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
Reset Code
Full screen
copy-code
Console