Subset MEX

Revision en3, by ashishdtu007, 2022-08-20 23:44:32

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)