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.
This approach involves the use of a greedy strategy combined with a set to track expressible numbers. We start by assuming that 1 is the smallest positive number and check if it is expressible as an OR of any subset of the input array 'nums'. If not, then it's the answer. If yes, move onto the next integer.
We maintain a set of all expressible numbers and keep checking the smallest number incrementally. The first number not found in this set will be the answer.
This C program uses an array to track expressible numbers up to the maximum value supported by an integer. Each number is checked whether it can be formed by taking the OR of any combination of the given numbers, updating the expressible array accordingly.
Time Complexity: O(n * (2^n)), where 'n' is the number of elements in 'nums'.
Space Complexity: O(1), using an array to track expressible numbers.
This approach incorporates dynamic programming using a bitmask technique to systematically check which numbers can be expressed by tracking the outcomes of OR operations. It capitalizes on the fact that the OR operation essentially behaves as a bitwise union, and thereby supports an incremental approach to generating numbers.
This solution minimizes unnecessary recalculation by storing the results of subsets and iterating through them to build up new possible numbers through DP transitions.
The C program uses a fixed-size array to implement a naive version of bitmask DP, storing reachable numbers from OR operations. It verifies results from left to right, updating the bitmask representation.
Time Complexity: O(32 * n), since we iterate through a fixed bitmask length.
Space Complexity: O(32), due to the bitmask storage structure.
We start from the integer 1. If 1 is expressible, it must appear in the array nums. If 2 is expressible, it must also appear in the array nums. If both 1 and 2 are expressible, then their bitwise OR operation 3 is also expressible, and so on.
Therefore, we can enumerate the powers of 2. If the currently enumerated 2^i is not in the array nums, then 2^i is the smallest unexpressible integer.
The time complexity is O(n + log M), and the space complexity is O(n). Here, n and M are the length of the array nums and the maximum value in the array nums, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Checking with Set | Time Complexity: O(n * (2^n)), where 'n' is the number of elements in 'nums'. Space Complexity: O(1), using an array to track expressible numbers. |
| Approach 2: Bitmask Dynamic Programming | Time Complexity: O(32 * n), since we iterate through a fixed bitmask length. Space Complexity: O(32), due to the bitmask storage structure. |
| Enumerate Powers of 2 | — |
| 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 |
2568. Minimum Impossible OR | LeetCode Medium | Bitwise OR • Deep Tech • 453 views views
Watch 8 more video solutions →Practice Minimum Impossible OR with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor