Subset MEX

Revision en2, by ashishdtu007, 2022-08-20 23:42:17

A subsequence is obtained by deleting some(possibly zero) elements of a sequence without changing the order of the elements in the sequence.

Given an array of n non-negative integers, find the smallest non-negative integer that can not be obtained as a bitwise OR of some subsequence of the given array. The bitwise OR of empty subsequence is 0.

example given arr = [1,3] output: 2

explanation: [] -> bitwise OR is 0 [1] -> bitwise OR is 1 [1,3] -> bitwise OR is 3 [3] -> bitwise OR is 3 so 2 is the smallest non-negative integer that is not possible to form using the bitwise OR of a subsequence of the given array.

Constraints : 1 <= n <= 10^5 0 <= arr[i] <= 10^9

Please help in upsolving this problem. Any ideas, hints or solutions will be helpful.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English ashishdtu007 2022-08-20 23:44:32 15 Tiny change: '\nA subseque' -> 'A subseque'
en2 English ashishdtu007 2022-08-20 23:42:17 3 Tiny change: '\nin the subsequence.\' -> '\nin the sequence.\'
en1 English ashishdtu007 2022-08-20 23:41:37 796 Initial revision (published)