Minimum Impossible OR solution and explanation
8 more videos on this problem
C. Minimum Impossible OR - LEETCODE BIWEEKLY CONTEST 98 (Code + Explanation in details)Joyjit Codes · 4:07 · 547 views
2568. Minimum Impossible OR | LeetCode Medium | Bitwise ORDeep Tech · 7:16 · 459 views
【每日一题】LeetCode 2568. Minimum Impossible ORHuifeng Guan · 11:00 · 284 views
2568. Minimum Impossible OR (Leetcode Medium)Programming Live with Larry · 10:21 · 213 views
LeetCode Biweekly Contest 98 : Problem 2568-Minimum Impossible OR |pls watch till end to understandCode With Singh · 8:17 · 203 views
Minimum Impossible OR | Leetcode 2568 | BiWeekly 98Tech Courses · 8:18 · 196 views
2568. Minimum Impossible OR | LeetCode Biweekly Contest 98Gaurav Agrawal · 8:39 · 135 views
2568. Minimum Impossible OR - Bi-Weekly Contest 98 (Detailed explanation + Code)Sourin Majumdar · 9:21 · 89 views
Leetcode biweeklycontest-98 A,B,C |2568 Min Impossible OR| 2566 Max Diff by Remap a Dig| 19/2/23CodingVerse · 19:19 · 22 views
The problem
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 <= 1051 <= 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.
def find_minimum_impossible(nums):
expressible = set([0])
for num in nums:
expressible.update({x | num for x in expressible})
ans = 1
while ans in expressible:
ans += 1
return ans
nums = [2, 1]
print(f"Minimum impossible OR: {find_minimum_impossible(nums)}")import java.util.HashSet;
public class MinImpossibleOR {
public static int findMinimumImpossible(int[] nums) {
HashSet<Integer> expressible = new HashSet<>();
expressible.add(0);
for (int num : nums) {
HashSet<Integer> newValues = new HashSet<>();
for (int x : expressible) {
newValues.add(x | num);
}
expressible.addAll(newValues);
}
int ans = 1;
while (expressible.contains(ans)) ans++;
return ans;
}
public static void main(String[] args) {
int[] nums = {2, 1};
System.out.println("Minimum impossible OR: " + findMinimumImpossible(nums));
}
}#include <iostream>
#include <set>
#include <vector>
int findMinimumImpossible(std::vector<int>& nums) {
std::set<int> expressible;
expressible.insert(0);
for (int num : nums) {
std::set<int> newValues;
for (int x : expressible) {
newValues.insert(x | num);
}
expressible.insert(newValues.begin(), newValues.end());
}
int ans = 1;
while (expressible.count(ans)) ans++;
return ans;
}
int main() {
std::vector<int> nums = {2, 1};
std::cout << "Minimum impossible OR: " << findMinimumImpossible(nums) << std::endl;
return 0;
}function findMinimumImpossible(nums) {
let expressible = new Set([0]);
for (let num of nums) {
let newValues = new Set();
for (let x of expressible) {
newValues.add(x | num);
}
newValues.forEach(value => expressible.add(value));
}
let ans = 1;
while (expressible.has(ans)) ans++;
return ans;
}
const nums = [2, 1];
console.log(`Minimum impossible OR: ${findMinimumImpossible(nums)}`);#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
int findMinimumImpossible(int* nums, int numsSize) {
bool expressible[INT_MAX] = {false};
expressible[0] = true;
for (int i = 0; i < numsSize; i++) {
for (int j = 0; j < (1 << numsSize); j++) {
if (expressible[j]) {
expressible[j | nums[i]] = true;
}
}
}
for (int i = 1; i < INT_MAX; i++) {
if (!expressible[i]) return i;
}
return -1; // Should never reach here ideally
}
int main() {
int nums[] = {2, 1};
int size = sizeof(nums) / sizeof(nums[0]);
printf("Minimum impossible OR: %d\n", findMinimumImpossible(nums, size));
return 0;
}using System;
using System.Collections.Generic;
public class MinImpossibleOR {
public static int FindMinimumImpossible(int[] nums) {
var expressible = new HashSet<int> { 0 };
foreach (var num in nums) {
var newValues = new HashSet<int>();
foreach (var x in expressible) {
newValues.Add(x | num);
}
expressible.UnionWith(newValues);
}
int ans = 1;
while (expressible.Contains(ans)) ans++;
return ans;
}
public static void Main() {
int[] nums = { 2, 1 };
Console.WriteLine("Minimum impossible OR: " + FindMinimumImpossible(nums));
}
}This Python solution uses a set to keep track of expressible integers, which are updated by computing OR with each number in 'nums'. The answer is determined by finding the first integer not present in this set.
Time Complexity: O(n^2) in the worst-case, due to the overhead of updating and checking a set for every possible bitwise operation.
Space Complexity: O(n).
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.
def find_minimum_impossible(nums):
dp = [False] * 32
dp[0] = True
for num in nums:
for i in range(31, -1, -1):
if dp[i]:
dp[i | num] = True
for i in range(1, 32):
if not dp[i]:
return i
return 32
print(f"Minimum impossible OR: {find_minimum_impossible([2, 1])}")import java.util.*;
public class MinImpossibleOR {
public static int findMinimumImpossible(int[] nums) {
boolean[] dp = new boolean[32];
dp[0] = true;
for (int num : nums) {
for (int i = 31; i >= 0; i--) {
if (dp[i]) dp[i | num] = true;
}
}
for (int i = 1; i < 32; i++) {
if (!dp[i]) return i;
}
return 32;
}
public static void main(String[] args) {
int[] nums = {2, 1};
System.out.println("Minimum impossible OR: " + findMinimumImpossible(nums));
}
}#include <iostream>
#include <vector>
int findMinimumImpossible(std::vector<int> &nums) {
std::vector<bool> dp(32, false);
dp[0] = true;
for (int num : nums) {
for (int i = 31; i >= 0; i--) {
if (dp[i]) dp[i | num] = true;
}
}
for (int i = 1; i < 32; i++) {
if (!dp[i]) return i;
}
return 32;
}
int main() {
std::vector<int> nums = {2, 1};
std::cout << "Minimum impossible OR: " << findMinimumImpossible(nums) << std::endl;
return 0;
}function findMinimumImpossible(nums) {
let dp = new Array(32).fill(false);
dp[0] = true;
for (let num of nums) {
for (let i = 31; i >= 0; i--) {
if (dp[i]) dp[i | num] = true;
}
}
for (let i = 1; i < 32; i++) {
if (!dp[i]) return i;
}
return 32;
}
console.log(`Minimum impossible OR: ${findMinimumImpossible([2, 1])}`);#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
int findMinimumImpossible(int* nums, int numsSize) {
int dp[32]; // Assuming 32-bit
for (int i = 0; i < 32; i++) {
dp[i] = 0;
}
dp[0] = 1; // The first possible OR (0 OR 0) is 0
for (int i = 0; i < numsSize; i++) {
for (int j = 31; j >= 0; j--) {
if (dp[j]) dp[j | nums[i]] = 1; // DP transition
}
}
int out = 1;
while (out < 32 && dp[out]) out++;
return out;
}
int main() {
int nums[] = {2, 1};
int size = sizeof(nums) / sizeof(nums[0]);
printf("Minimum impossible OR: %d\n", findMinimumImpossible(nums, size));
return 0;
}using System;
public class MinImpossibleOR {
public static int FindMinimumImpossible(int[] nums) {
bool[] dp = new bool[32];
dp[0] = true;
foreach (var num in nums) {
for (int i = 31; i >= 0; i--) {
if (dp[i]) dp[i | num] = true;
}
}
for (int i = 1; i < 32; i++) {
if (!dp[i]) return i;
}
return 32;
}
public static void Main() {
int[] nums = { 2, 1 };
Console.WriteLine("Minimum impossible OR: " + FindMinimumImpossible(nums));
}
}A bitmask-driven DP approach in Python, leveraging indices against the true/false state to predict OR results based combinations as derived from the elements in 'nums'.
Time Complexity: O(32 * n), due to bitmask limitations and available calculations per OR.
Space Complexity: O(32), reflecting the bitmask size.
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.
function minImpossibleOR(nums: number[]): number {
const s: Set<number> = new Set();
for (const x of nums) {
s.add(x);
}
for (let i = 0; ; ++i) {
if (!s.has(1 << i)) {
return 1 << i;
}
}
}func minImpossibleOR(nums []int) int {
s := map[int]bool{}
for _, x := range nums {
s[x] = true
}
for i := 0; ; i++ {
if !s[1<<i] {
return 1 << i
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Checking with Set | Time Complexity: O(n^2) in the worst-case, due to the overhead of updating and checking a set for every possible bitwise operation. Space Complexity: O(n). |
| Approach 2: Bitmask Dynamic Programming | Time Complexity: O(32 * n), due to bitmask limitations and available calculations per OR. Space Complexity: O(32), reflecting the bitmask size. |
| Enumerate Powers of 2 | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Checking with Set | O(n) | O(n) | Best general solution; quickly detects the smallest missing power of two |
| Bitmask Dynamic Programming | O(n * B) | O(2^B) | Useful for understanding all reachable OR values or when constraints are very small |
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.