We are given an array of length N. We have to find the minimum length subset( not subarray) of array with maximum OR value.
N bound till 10^5. Ai<=10^6
Only one example was given:
Array elements are 1,2,3,4,5
possible max OR is 7. Minimum length subset are (5,2) and (3,4)
Can u please post the link of the question?
link is not active now. It was a hiring question
@vivek_1998299 I think we can solve it using Dynamic Programming, though I am not sure as I can not verify it because I did not find this problem posted any online judge/ interview site where I can submit solution. Would like to know your insight.
I think I saw such a question in a past contest 
. It involved dp.
I tried a dp. Recursive with memoization. First i found out OR of all elements which is actually maximum. Then made a boolean array req[30] which tells whether ith bit is required or not.
Initally count=0(number of elements taken) and index=0. I call dp(req,0,0). For element at index i find out whether it can satisfy any required bit. If yes then there can be two cases- take it or not.So i return minimum of( dp(newreq,cnt+1, ind+1) and dp(req,cnt,ind+1). If not then there is no need to include that element so simply return dp(req,cnt,ind+1).
The terminating condition is if( index>= array length), check if req array has a true value or not. If yes that means we failed to obtain max OR so return Integer.MAX_VALUE( as we are taking min above). If there is no true value that means that the number is obtained so return count.
So you did not get a right answer? Where were you stuck? I am yet to appear for any interview but from what I have heard, interviewee is looking more for your approach to solve the question rather than question itself. And even with the Brute Force approach(O(2^N)) you must have got some partial acceptance from the interviewee?
I faced the same problem in a hiring contest of a company I cracked and managed to get all the test-cases accepted with a simple hack in the O(n^2) algorithm by using a break whenever an element was useless (i.e did not increase the overall current value of OR of the subset in consideration). I am unable to find the code and think of the exact solution right now but it’s surely not the optimal solution. I got lucky with the trick and all the test-cases barely passing.
I really have no idea on how to solve this.Initially i thought ,that since this problem is reducible to set covering ,it must be np-hard,but since the set size is no more than 20,i think i could have an optimal solution,but i cant find it 
Like 1,2,3,4,5 can be represented as sets
{1},{2},{1,2},{4},{1,4}
and basically u want to get the set {1,2,4} taking union of as minimum sets as possible
Yeah i know. That’s why i said i tried a dp
@dwij28 i think i could have optimized the solution a little bit more but then also it wouldn’t be a optimal solution
Can anyone help please?
The best I could think of is 3^{log(max(a_i))}.
finding the max or is easy. consider binary representation of a number to be it’s mask.
now for a mask m let dp[m] be minimum no. of elements required such that their or is a supermask of m. so if m=6=110. then both 2,4 and 2,5 are valid choice. notice that 2,5 produces 111 but is still valid as we need a super mask.
now calculating the dp.
First remove all duplicates in a. it’s easy to see this won’t change the answer.
Initialize dp to infinity. Now for each element in a initialize dp[a$_i$] to 1 and also each of it’s submasks. Now lets say a$_i$ has k bits set in it. then it has 2$^k$ submasks.
so the entire initialization process costs \Sigma_{k=0}^{k=20} C(20,k)2$^k$. this by binomial expansion is (1+2)^{20} which is 3$^{20}$.
Now start calculating each dp[m] in incresing order of no. of bits set in m.
for each mask m consider every submask p. dp[m]=min(dp[m],dp[p]+dp[m^p]).
this relation means if p can be obtained in n1 items and m^p(which is completment of p wrt m) can be obtained from n2 items. then since their or is m, m can be obtained in n1+n2 elements.
again total no. of submasks if 2^k and therefore takes total time of 3^{20}.
final answer is dp[OR].
If any part is not clear you can ask me. Or if I’m wrong point it out. This would work easily for a$_i$<=1e5 but will tl for 1e6. maybe someone can think of some optimization.
Max ai is 10^6. So 3^20 will get TLE.
I guess it can be modelled as a vertex cover problem. We can easily find what is the maximum OR possible. Now keep only those bits and draw edges with the elements for which those bits are set. Now problem is finding minimum vertex cover. Correct me if I am wrong.
Not sure dear
Okay minimum vertex cover actually works. Model the problem as i told above. Now I am explaining why it gives correct answer. Focus on the defination of vertex cover. “Each edge must have an end point in the selected subset”. Now assume after selecting a subset of vertices my ith bit doesnt get set(Note it must be set in actual ans i.e max OR). Now this in turn means no edge having end points in ith bit has a end point in the selected subset. WHY? Because if the edge had an end point and it was not ith bit then it must be a[j] where ith bit is set in a[j]. So ith bit gets set which is contradiction. Hence all the bits get set after considering the minimum vertex cover. Also it passes in time as E=nlogn here.