How to find minimum size subset of an array with maximum OR

Правка en1, от VBT, 2018-06-23 12:06:10

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.

Теги bits, #bitwiseor

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский VBT 2018-06-23 12:06:10 541 Initial revision (published)