Problem

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 minimumpositive non-zero integer that is not _expressible fromnums.

Examples

Example 1

1
2
3

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

1
2
3

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 <= 10^5
  • 1 <= nums[i] <= 10^9

Solution

Method 1 – Check for Missing Power of Two

Intuition

The only way a positive integer cannot be expressed as the OR of a subset is if it is a power of two that cannot be formed from the available numbers. If all powers of two up to a certain value can be formed, the next missing power of two is the answer.

Approach

  1. Put all numbers in a set for fast lookup.
  2. Start from 1 and check if it is present in the set.
  3. If not present, return it as the answer.
  4. If present, multiply by 2 and repeat.

Code

1
2
3
4
5
6
7
8
9

class Solution {
public:
    int minImpossibleOR(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int x = 1;
        while (s.count(x)) x <<= 1;
        return x;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func minImpossibleOR(nums []int) int {
    s := make(map[int]struct{})
    for _, x := range nums {
        s[x] = struct{}{}
    }
    x := 1
    for {
        if _, ok := s[x]; !ok {
            return x
        }
        x <<= 1
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    public int minImpossibleOR(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int x : nums) s.add(x);
        int x = 1;
        while (s.contains(x)) x <<= 1;
        return x;
    }
}
1
2
3
4
5
6
7
8

class Solution {
    fun minImpossibleOR(nums: IntArray): Int {
        val s = nums.toSet()
        var x = 1
        while (x in s) x = x shl 1
        return x
    }
}
1
2
3
4
5
6

def min_impossible_or(nums: list[int]) -> int:
    s = set(nums)
    x = 1
    while x in s:
        x <<= 1
    return x
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

impl Solution {
    pub fn min_impossible_or(nums: Vec<i32>) -> i32 {
        let s: std::collections::HashSet<_> = nums.into_iter().collect();
        let mut x = 1;
        while s.contains(&x) {
            x <<= 1;
        }
        x
    }
}
1
2
3
4
5
6
7
8

class Solution {
    minImpossibleOR(nums: number[]): number {
        const s = new Set(nums);
        let x = 1;
        while (s.has(x)) x <<= 1;
        return x;
    }
}

Complexity

  • ⏰ Time complexity: O(n log M), where n is the length of nums and M is the maximum value in nums. Each power of two is checked up to the maximum value.
  • 🧺 Space complexity: O(n), for storing the set of numbers.