lee5's blog

By lee5, history, 7 weeks ago, In English

Can someone help me with this problem? Given an array of integers. Find the smallest positive integer which cannot be formed by performing bitwise OR on all the elements of a chosen subset. I don't know the range of n(size of the array), but what can be the most optimized approach?

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Problem source?

»
7 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

The answer is the smallest power of two (or zero) which is not in the input. Since you can only generate a power of two if it is in the input. All smaller numbers can be generated from a combination of the smaller powers of two.