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.

#2568

Medium

auto_awesome数组·结合·位运算·操作

LeetCode 题解工作台

最小无法得到的或值

给你一个下标从 0 开始的整数数组 nums 。如果存在一些整数满足 0 1 2 k ，得到 nums[index 1 ] | nums[index 2 ] | ... | nums[index k ] = x ，那么我们说 x 是可表达的。换言之，如果一个整数能由 nums 的某个子序列的或…

数组位运算脑筋急转弯

题目描述

给你一个下标从 0 开始的整数数组 nums 。

如果存在一些整数满足 0 <= index₁ < index₂ < ... < index_k < nums.length ，得到 nums[index₁] | nums[index₂] | ... | nums[index_k] = x ，那么我们说 x 是 可表达的 。换言之，如果一个整数能由 nums 的某个子序列的或运算得到，那么它就是可表达的。

请你返回 nums 不可表达的 最小非零整数 。

示例 1：

输入：nums = [2,1]
输出：4
解释：1 和 2 已经在数组中，因为 nums[0] | nums[1] = 2 | 1 = 3 ，所以 3 是可表达的。由于 4 是不可表达的，所以我们返回 4 。

示例 2：

输入：nums = [5,3,2]
输出：1
解释：1 是最小不可表达的数字。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：枚举 2 的幂

我们从整数 $1$ 开始考虑，如果 $1$ 是可表达的，那么它必须出现在数组 nums 中；如果 $2$ 是可表达的，那么它必须出现在数组 nums 中；如果 $1$ 和 $2$ 都是可表达的，那么它们的或运算 $3$ 也是可表达的，以此类推。

因此，我们可以枚举 $2$ 的幂，如果当前枚举的 $2^i$ 不在数组 nums 中，那么 $2^i$ 就是不可表达的最小整数。

时间复杂度 $O(n + \log M)$ ，空间复杂度 $O(n)$ 。其中 $n$ 和 $M$ 分别是数组 nums 的长度和数组 nums 中的最大值。

1

2

3

4

5

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)

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on cumulative bit coverage and subsequence ORs
question_mark
Check for powers of two gaps to identify missing numbers
question_mark
Efficiency matters: avoid generating all subsequences explicitly

warning

常见陷阱

外企场景

error
Assuming the missing number is max(nums)+1 without checking OR combinations
error
Enumerating all subsequences leading to timeouts
error
Ignoring bitwise properties leading to incorrect smallest number

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find maximum number not expressible using at most k elements
arrow_right_alt
Handle arrays with negative numbers and modified OR rules
arrow_right_alt
Compute count of unexpressible integers under given constraints

help

常见问题

外企场景

继续练习

#2425 所有数对的异或和 #2419 按位与最大的最长子数组 #2564 子字符串异或查询