Skip to content

2568. Minimum Impossible OR

Description

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

Solutions

Solution 1: Enumerate Powers of 2

Thinking

A value is expressible if it is the bitwise OR of some nonempty subset. OR only turns bits on, so if every power below \(2^k\) is present, every integer in \([1,2^{k+1}-1]\) is expressible.

The smallest missing value is therefore a missing power of two. Store the array in a set and return the first \(2^i\) that is absent.

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.

1
2
3
4
class Solution:
    def minImpossibleOR(self, nums: List[int]) -> int:
        s = set(nums)
        return next(1 << i for i in range(32) if 1 << i not in s)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int minImpossibleOR(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int x : nums) {
            s.add(x);
        }
        for (int i = 0;; ++i) {
            if (!s.contains(1 << i)) {
                return 1 << i;
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int minImpossibleOR(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        for (int i = 0;; ++i) {
            if (!s.count(1 << i)) {
                return 1 << i;
            }
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
        }
    }
}

Comments