Minimum Impossible OR — Solution in Python, Java & C++
Minimum Impossible OR solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Impossible OR is a medium coding problem on arrays, bit manipulation and brainteaser, asked in Amazon, Google and Arcesium interviews.
- Difficulty: Medium
- Topics: Arrays, Bit Manipulation, Brainteaser
- Asked at: Amazon, Google, Arcesium
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An integer x is expressible from nums if some non-empty subsequence of nums has bitwise OR exactly x.
Return the smallest positive integer that is not expressible.
Example 1
Input: nums = [2,1]
Output: 4
Explanation: 1, 2 and 3 are all reachable; 4 is not.
Example 2
Input: nums = [5,3,2]
Output: 1
Explanation: No subsequence ORs to 1.
Example 3
Input: nums = [1,2,4,8]
Output: 16
Constraints
1 <= nums.length <= 1000001 <= nums[i] <= 1000000000
Hints for Minimum Impossible OR
Hint 1
OR only ever sets bits, so a value with several bits is reachable once each of its bits is available on its own.
Hint 2
That makes the powers of two the only values that matter.
Hint 3
The answer is the smallest power of two missing from
nums.
How to solve Minimum Impossible OR
Only the powers of two present in nums matter: every non-power is an OR of the powers below it, and conversely a power of two can only come from an element equal to it.
Approach
- Put the values in a set.
- Walk
1, 2, 4, 8, …and return the first one missing.
Why it works
If 2^k is in nums for all k below some bound, every integer whose bits lie under that bound is the OR of the corresponding singletons — so all of them are expressible. Conversely, 2^k has one bit, so any subsequence ORing to it must consist entirely of elements that are themselves 2^k — meaning 2^k is expressible precisely when it appears. So the first missing power of two is the first inexpressible value.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Trying to enumerate subsequence ORs is exponential and unnecessary.
- A non-power like 3 being absent does not matter — it is
1 | 2. - The walk terminates quickly: at most 31 powers fit the value range.
Reference solution
Python
from typing import List
def minImpossibleOR(nums: List[int]) -> int:
have = set(nums)
p = 1
while p in have:
p *= 2
return pJava
public static int minImpossibleOR(int[] nums) {
Set<Integer> have = new HashSet<>();
for (int x : nums) have.add(x);
int p = 1;
while (have.contains(p)) p *= 2;
return p;
}C++
int minImpossibleOR(vector<int>& nums) {
unordered_set<int> have(nums.begin(), nums.end());
int p = 1;
while (have.count(p)) p *= 2;
return p;
}JavaScript
var minImpossibleOR = function(nums) {
var has = {};
for (var i = 0; i < nums.length; i++) has[nums[i]] = true;
var p = 1;
while (has[p]) p *= 2;
return p;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Bit Manipulation