#2568

Medium

LeetCode Problem Workspace

Minimum Impossible OR

Find the smallest positive integer that cannot be formed from any subsequence OR combination in the array.

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

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.

terminal

Solution

Solution 1: Enumerate Powers of 2

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.

1

2

3

4

class Solution:
    def minImpossibleOR(self, nums: List[int]) -> int:
        s = set(nums)
        return next(1 << i for i in range(32) if 1 << i not in s)

Continue Practicing

#2425 bitwise xor of all pairings #2419 longest subarray with maximum bitwise and #2564 substring xor queries