The solution focuses on identifying the smallest positive integer that cannot result from any subsequence OR operation of the array elements. By analyzing bit patterns and tracking achievable sums efficiently, we can compute the minimum impossible OR without enumerating all subsequences. This method avoids combinatorial explosion while correctly handling large arrays and high integer values.
Problem Statement
You are given a 0-indexed array nums of integers. An integer x is called expressible if it can be obtained by performing the bitwise OR operation on any non-empty subsequence of nums. For example, nums[index1] | nums[index2] | ... | nums[indexk] = x for some indices in the array.
Your task is to return the smallest positive integer that is not expressible from nums. For instance, given nums = [2,1], numbers 1, 2, and 3 are expressible, but 4 is not, so the output should be 4.
Examples
Example 1
Input: nums = [2,1]
Output: 4
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
We can show that 1 is the smallest number that is not expressible.
Constraints
- 1 <= nums.length <= 105
- 1 <= nums[i] <= 109
Solution Approach
Count Powers of Two and Track Coverage
Identify which powers of two are present in nums. Each missing power indicates the smallest OR that cannot be formed. This leverages the pattern that OR combinations are cumulative over bits, ensuring efficient detection of gaps.
Incremental OR Computation
Iterate through nums while maintaining a set of all OR results achievable so far. Add nums[i] OR every existing element in the set to track new expressible numbers. Stop once you find the first positive integer not in the set. This prevents full subsequence enumeration.
Greedy Bit Assembly
Start from 1 and check if it can be formed by combining available numbers' bits. If a number's bit is missing in all elements, it cannot be formed and is the minimum impossible OR. This method directly ties to the bit manipulation pattern and avoids unnecessary combinations.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity depends on the method: using bit tracking or set expansion is O(n * number_of_bits), space complexity is O(number_of_bits) or O(n) depending on tracking OR results. Full subsequence enumeration is infeasible.
What Interviewers Usually Probe
- Focus on cumulative bit coverage and subsequence ORs
- Check for powers of two gaps to identify missing numbers
- Efficiency matters: avoid generating all subsequences explicitly
Common Pitfalls or Variants
Common pitfalls
- Assuming the missing number is max(nums)+1 without checking OR combinations
- Enumerating all subsequences leading to timeouts
- Ignoring bitwise properties leading to incorrect smallest number
Follow-up variants
- Find maximum number not expressible using at most k elements
- Handle arrays with negative numbers and modified OR rules
- Compute count of unexpressible integers under given constraints
How GhostInterview Helps
- Quickly identify missing powers of two without full subsequence generation
- Track all reachable OR values efficiently to pinpoint the minimum impossible number
- Explain bitwise reasoning clearly to avoid combinatorial traps
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What does Minimum Impossible OR mean in this problem?
It is the smallest positive integer that cannot be obtained as a bitwise OR of any subsequence of nums.
Can we just take max(nums)+1 as the answer?
No, because OR combinations may form numbers beyond individual elements, so missing numbers can appear before max(nums)+1.
Why focus on powers of two?
Each bit represents a power of two, and missing bits in all numbers immediately indicate numbers that cannot be formed via OR.
Is enumerating all subsequences feasible?
No, this leads to exponential time complexity. Efficient bit tracking or OR accumulation is required.
How does bit manipulation help solve Minimum Impossible OR?
Bit manipulation reveals which sums are possible by combining bits, letting you detect the smallest number that cannot be formed efficiently.
Need direct help with Minimum Impossible OR instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Minimum Impossible OR from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Compute the overall bitwise XOR from all pairings between two arrays using efficient array and bit manipulation techniques.
Open problem page#2419 Longest Subarray With Maximum Bitwise ANDFind the length of the longest subarray whose bitwise AND reaches the array's maximum value, combining array scanning with bit manipulation logic.
Open problem page#2564 Substring XOR QueriesSolve the Substring XOR Queries problem using array scanning and hash lookup to efficiently handle multiple queries on binary strings.
Open problem page