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

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