VBT's blog

By VBT, history, 4 years ago, In English

Asked in a company's coding round. So i don't have a link for it now.

Given an array of length N we have to find the minimum size subset(not subarray) with maximum OR.

Constraints: N bound was till 10^5. Elements of array 0<=Ai<=10^6

Example given was: Array elements are {1,2,3,4,5} Max possible OR is the OR of all elements i.e. 7. But minimum size subset with same OR(7) are (5,2) and (3,4). So the answer is 2(their size). I tried a dp solution which got TLE.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it