Is Minimum Impossible OR easy or hard?

The problem is rated Medium because the solution depends on a key observation about bitwise OR and powers of two. Once the insight is recognized, the implementation becomes straightforward and runs in linear time.

Minimum Impossible OR Python/Java solution

The typical implementation inserts all numbers into a set and iterates through powers of two using a loop. Python, Java, C++, and other languages implement this in a few lines by checking membership in the set and shifting the power value left each iteration.

How to solve Minimum Impossible OR in O(n)?

Insert every number from the array into a hash set. Then iterate through powers of two starting from 1. The first power of two not found in the set is the smallest impossible OR value, because OR operations cannot isolate a bit that never appears alone in the input.

What is the best approach for Minimum Impossible OR?

The optimal approach checks for the smallest missing power of two in the array. Store all values in a hash set and iterate through 1, 2, 4, 8, ... until a power is missing. This works because producing exactly 2^k requires a number with only that bit set. The algorithm runs in O(n) time with O(n) space.

Is Minimum Impossible OR asked at Google/Amazon/Meta?

Problems involving bit manipulation and reasoning about OR/AND operations are common in interviews at companies like Google, Amazon, and Meta. This specific problem is categorized as a brainteaser-style bit manipulation question similar to what appears in technical screens.

What data structure is used in Minimum Impossible OR?

The primary data structure is a hash set used for constant-time membership checks. It allows quick verification of whether each power of two exists in the input array. The problem also relies heavily on bit manipulation concepts.

What is the time complexity of Minimum Impossible OR?

The optimal solution runs in O(n) time. Building a hash set from the array takes O(n), and checking powers of two requires only about 31–32 iterations for standard integer limits. Space complexity is O(n) due to the set.

Description Hints 2 Solution Video 4:07

2568. Minimum Impossible OR

Medium59.5% acceptance1 company

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 <= index₁ < index₂ < ... < index_k < nums.length for which nums[index₁] | nums[index₂] | ... | nums[index_k] = 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 <= 10⁵
1 <= nums[i] <= 10⁹

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

Think about forming numbers in the powers of 2 using their bit representation.

Hint 2

The minimum power of 2 not present in the array will be the first number that could not be expressed using the given operation.

4:07

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minImpossibleOR(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[2,1]

Input

[5,3,2]

Your code is saved on this device.Solution