Minimum Impossible OR

Problem Description

Given an integer array nums, we call a positive integer x “expressible” if there is some non‐empty subsequence of nums whose bitwise OR equals x. In other words, if you can choose some indices i₁ < i₂ < … < iₖ so that   nums[i₁] | nums[i₂] | … | nums[iₖ] = x, then x is expressible. The task is to return the minimum positive (nonzero) integer that is NOT expressible from nums.

For example, in nums = [2,1] the numbers 1 and 2 appear (each as a singleton) and 3 is expressible since 2|1 = 3, but 4 is not expressible so we return 4.

Key Insights

• Any subsequence OR is “monotonic” in the sense that when you OR several numbers you cannot “cancel” a 1–bit.
• In order to get an OR result equal exactly to a power of two (say 2ᵇ), one of the chosen numbers must be exactly 2ᵇ; if a number has extra bits then OR‐ing it will “force” more ones into the answer.
• In general, every expressible number x must be “covered” bit–by–bit by some elements from nums that are “clean” (i.e. they do not have any extra 1s not in x). In particular, to express any number that is exactly a power of two, an element equal to that power must appear in nums.
• It turns out that all expressible numbers are exactly those numbers whose 1–bits come from powers of two that occur as “singleton” elements in nums. (For example, if 1, 2 and 4 are present then any number from 1 to 7 is expressible – note that OR–combining these coins never “drops” a 1–bit, and a composite number always forces you to use an element that covers several bits at once.)
• Therefore, the minimum “impossible” result is simply the smallest power of two that does not appear in nums; if every power 2ᵇ (for every b that occurs in the bit–representation of some number in nums) is present then all numbers having only those bits can be obtained and the next impossible number is 2^(max_bit+1).

Space and Time Complexity

Time Complexity: O(n + B) where n is the length of nums and B is the number of bits (at most 32)
Space Complexity: O(n) (to store the set of numbers that appear in nums; the extra space for bit–checking is O(1))

Solution

The key observation is that if you want to express a number which is exactly a power of two (say 2ᵇ), you cannot “assemble” it by OR‐ing together other numbers because any number with 2ᵇ set that is not exactly 2ᵇ has at least one extra 1–bit. (For example, if you have 3 = 0…011, you cannot “split” it to get 2 = 0…010.)
Thus, in order for every number having only one bit to be expressible, every power of two that might be needed must appear in nums. In other words, consider the set of “coins” formed by the numbers in nums that are exactly a power of two. Then every expressible number is obtained by OR–combining a subset of these coins. In particular, the expressible numbers are exactly all numbers whose binary representation consists only of those bits for which nums contains a corresponding “coin.”
So the smallest positive integer that is not expressible is the smallest power of two (i.e. 2ᵇ for some b) that is missing in nums. (If for every bit that ever occurs in any element of nums there is an element equal to that power of two then any number that is a submask of the union is expressible; in that case the first “gap” comes from adding a new bit – namely 2^(max_bit+1).)

The algorithm is as follows:

1. Loop over nums and build a set (or hash table) containing all numbers.
2. For bit positions b = 0, 1, 2, … (up to 31), check whether 2ᵇ appears in nums.
3. If you find a power 2ᵇ that is not present, return it.
4. If all such powers are present (up to the highest bit seen), then return 2^(max_bit+1) as the answer.

This works because—as argued—the necessary “building blocks” for forming numbers by OR–operations are exactly the pure powers of two. (Any composite number in nums cannot be “split” into its component bits because you are allowed to use an element only once.)

Code Solutions