Watch 9 video solutions for Minimum Impossible OR, a medium level problem involving Array, Bit Manipulation, Brainteaser. This walkthrough by Deep Tech has 453 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array nums.
We say that an integer x is expressible from nums if there exist some integers 0 <= index1 < index2 < ... < indexk < nums.length for which nums[index1] | nums[index2] | ... | nums[indexk] = x. In other words, an integer is expressible if it can be written as the bitwise OR of some subsequence of nums.
Return the minimum positive non-zero integer that is not expressible from nums.
Example 1:
Input: nums = [2,1] Output: 4 Explanation: 1 and 2 are already present in the array. We know that 3 is expressible, since nums[0] | nums[1] = 2 | 1 = 3. Since 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 <= 1051 <= nums[i] <= 109Problem Overview: You are given an integer array nums. You can take any subsequence and compute the bitwise OR of its elements. The task is to return the smallest positive integer that cannot be produced by OR-ing any subsequence.
Approach 1: Iterative Checking with Set (O(n) time, O(n) space)
The key observation is that the smallest impossible OR must always be a power of two. To produce a value like 2^k, you must have an element with exactly that bit set. If every number contributing to the OR has additional bits, the result will contain those bits as well, so you can never isolate a single missing bit. Store all numbers in a hash set, then iterate through powers of two (1, 2, 4, 8, ...). The first power that does not appear in the set is the answer. This works because if all powers up to 2^k exist, you can combine them with OR to construct any number whose bits are within that range. The first missing power-of-two therefore becomes the minimum impossible value. This solution mainly relies on efficient hash lookups and properties of bit manipulation combined with simple iteration over the array.
Approach 2: Bitmask Dynamic Programming (O(n * B) time, O(2^B) space)
Another way is to explicitly track all OR results achievable from subsequences. Maintain a set (or boolean DP structure) of reachable OR values. For each number, update the set by OR-ing it with every previously reachable value. This resembles subset-style dynamic programming where states represent achievable bitmasks. After processing all elements, scan positive integers starting from 1 and return the first value not present in the reachable set. The approach is conceptually straightforward but can grow large if many OR combinations appear, making it less practical for large inputs.
Recommended for interviews: The iterative power-of-two check is the expected solution. It shows you understand how OR operations propagate bits and why a missing single-bit value blocks construction of certain results. The DP method demonstrates correctness but is usually unnecessary and less efficient.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Checking with Set | O(n) | O(n) | Best general solution; quickly detects the smallest missing power of two |
| Bitmask Dynamic Programming | O(n * B) | O(2^B) | Useful for understanding all reachable OR values or when constraints are very small |