2568. Minimum Impossible OR LeetCode Solution

In this guide, you will get 2568. Minimum Impossible OR LeetCode Solution with the best time and space complexity. The solution to Minimum Impossible OR problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Impossible OR solution in C++
4. Minimum Impossible OR solution in Java
5. Minimum Impossible OR solution in Python
6. Additional Resources

Problem Statement of Minimum Impossible OR

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

Complexity Analysis

• Time Complexity: O(n + 32) = O(n)
• Space Complexity: O(n)

2568. Minimum Impossible OR LeetCode Solution in C++

class Solution {
 public:
  int minImpossibleOR(vector<int>& nums) {
    int ans = 1;
    const unordered_set<int> numsSet{nums.begin(), nums.end()};

    while (numsSet.contains(ans))
      ans <<= 1;

    return ans;
  }
};
/* code provided by PROGIEZ */

2568. Minimum Impossible OR LeetCode Solution in Java

class Solution {
  public int minImpossibleOR(int[] nums) {
    int ans = 1;
    Set<Integer> numsSet = Arrays.stream(nums).boxed().collect(Collectors.toSet());

    while (numsSet.contains(ans))
      ans <<= 1;

    return ans;
  }
}
// code provided by PROGIEZ

2568. Minimum Impossible OR LeetCode Solution in Python

class Solution:
  def minImpossibleOR(self, nums: list[int]) -> int:
    ans = 1
    numsSet = set(nums)

    while ans in numsSet:
      ans <<= 1

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.