C++     Medium    

Problem Statement:

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

Solution:

Intuition

This problem seems similar to First Missing Positive. Here is a solution to that probelm:

 
int firstMissingPositive(vector<int>& nums) {
    unordered_set<int> numSet(nums.begin(),nums.end());
    int i = 1;
    while (i <= nums.size()){
        if (!numSet.count(i)) return i;
        i++;
    }
    return i;
}

Observation

Our solution is similar to the above in spirit. The crucial thing to notice is that if we have just powers of 2, we can construct all numbers upto the next power of 2 by their OR.

For example, given the array [1,2,4,8,16], we can do OR between various elements to construct all numbers from 1 to 31. So the presence of other numbers in the middle like 3,5,6 etc. does not change the range of possible numbers. Hence these are the only ones that need to be checked.

Code

 
class Solution {
public:
    int minImpossibleOR(vector<int>& nums) 
    {
        unordered_set<int> numSet(nums.begin(),nums.end());
        int cur = 1;
        while (cur<INT_MAX)
        {
            if (!numSet.count(cur)) return cur;
            cur <<= 1;
        }
        return INT_MAX;
    }
};