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.
Since the OR function requires set bits or powers of 2, the first power of 2 which is not in the array should be the answer? For example if we have [1, 2, 4] then 1, 2, ..., 7 are all possible although 8 is not hence that is the answer.