Skip to main content
Talentd

Minimum Impossible OR - Solution & Explanation

MediumArrayBit ManipulationBrainteaser17 min readAsked at: Amazon
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 109

Approach Overview

Problem 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.

Approach 1: Approach 1: Iterative Checking with Set

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Bitmask Dynamic Programming

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(32 * n), since we iterate through a fixed bitmask length.

Space Complexity: O(32), due to the bitmask storage structure.

Try this approach in the editor →

Approach 3: 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.

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Checking with SetO(n)O(n)Best general solution; quickly detects the smallest missing power of two
Bitmask Dynamic ProgrammingO(n * B)O(2^B)Useful for understanding all reachable OR values or when constraints are very small

Video Solution

C. Minimum Impossible OR - LEETCODE BIWEEKLY CONTEST 98 (Code + Explanation in details) • Joyjit Codes • 547 views views

Watch 8 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Minimum Impossible OR with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays