4 is not expressible, we return 4.

Example 2

Input: nums = [5,3,2]
Output: 1
Explanation: We can show that 1 is the smallest number that is not expressible.

Constraints

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

Solution

Method 1 – Check for Missing Power of Two

Intuition

The only way a positive integer cannot be expressed as the OR of a subset is if it is a power of two that cannot be formed from the available numbers. If all powers of two up to a certain value can be formed, the next missing power of two is the answer.

Approach

Put all numbers in a set for fast lookup.
Start from 1 and check if it is present in the set.
If not present, return it as the answer.
If present, multiply by 2

Related Tags