Get started

Minimum Impossible OR — Medium Problem & Solution

An integer x is expressible from nums if some non-empty subsequence of nums has bitwise OR exactly x.

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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue