When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

VBT's blog

By VBT, history, 6 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.

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