Minimum Impossible OR

Medium
864.

Minimum Impossible OR

Minimum Impossible OR is a medium coding problem on arrays, bit manipulation and brainteaser, asked in Amazon, Google and Arcesium interviews.

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 <= 100000
  • 1 <= nums[i] <= 1000000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minImpossibleOR = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 100000
  • 1 <= nums[i] <= 1000000000

Hints for Minimum Impossible OR

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

  2. Hint 2

    That makes the powers of two the only values that matter.

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

  1. Put the values in a set.
  2. 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 p

Java

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