# Minimum Impossible OR
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-impossible-or)
Canonical: https://scaleengineer.com/dsa/problems/minimum-impossible-or
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
---
## 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 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`

# Approaches
## Brute-Force by Generating All Subsequences
This approach directly follows the definition of expressible numbers. It generates every possible non-empty subsequence of the input array `nums`. For each subsequence, it computes the bitwise OR of its elements. All such resulting values are stored in a set to keep track of all unique expressible numbers. Finally, it iterates through positive integers starting from 1 and returns the first integer not found in the set of expressible numbers.
**Time:** O(N * 2^N). There are `2^N` subsequences, and calculating the OR for each takes up to O(N) time. · **Space:** O(min(2^N, M)), where M is the maximum possible OR value. The set can store up to `2^N` distinct values in the worst case.
**Pros:** Conceptually simple and directly follows the problem statement.
**Cons:** Extremely inefficient due to its exponential time complexity.; Not feasible for the given constraints (`N` up to 10^5).; Will result in Time Limit Exceeded and Memory Limit Exceeded for large inputs.
### Explanation
The algorithm iterates through all `2^N - 1` non-empty subsequences of the input array `nums`, where `N` is the length of the array. This is typically done using a bitmask, where each integer from `1` to `2^N - 1` represents a unique subsequence. The `j`-th bit of the integer corresponds to the `j`-th element of `nums`. If the bit is set, the element is included in the subsequence's OR calculation. After computing all possible OR values and storing them, the algorithm performs a linear scan starting from 1 to find the first positive integer that was not generated.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minImpossibleOR(int[] nums) {
        Set<Integer> expressibleNumbers = new HashSet<>();
        int n = nums.length;
        // Iterate through all possible non-empty subsequences using a bitmask
        for (int i = 1; i < (1 << n); i++) {
            int currentOr = 0;
            for (int j = 0; j < n; j++) {
                // Check if the j-th element is in the subsequence
                if ((i & (1 << j)) != 0) {
                    currentOr |= nums[j];
                }
            }
            expressibleNumbers.add(currentOr);
        }

        int missingNumber = 1;
        while (true) {
            if (!expressibleNumbers.contains(missingNumber)) {
                return missingNumber;
            }
            missingNumber++;
        }
    }
}
```
### Algorithm
- Initialize an empty `HashSet` called `expressibleNumbers`.
- Generate all `2^N - 1` non-empty subsequences of `nums` using a bitmask from `1` to `(1 << N) - 1`.
- For each subsequence:
    - Calculate the bitwise OR of all its elements, let the result be `orValue`.
    - Add `orValue` to the `expressibleNumbers` set.
- Initialize a variable `missingNumber` to 1.
- Loop indefinitely:
    - If `missingNumber` is not in `expressibleNumbers`, return it.
    - Otherwise, increment `missingNumber`.

## Building the Set of Expressible Numbers Iteratively
This approach avoids generating subsequences explicitly. Instead, it builds the set of all expressible numbers iteratively. It starts with the numbers present in the input array. Then, it repeatedly takes a number from the set of newly found expressible numbers and ORs it with every number from the original array, adding any new results back to the set. This process continues until no new expressible numbers can be generated. Finally, it finds the smallest positive integer not in this complete set.
**Time:** O(U * |E|), where `U` is the number of unique elements in `nums` and `|E|` is the total number of expressible values. In the worst case, this is too slow. · **Space:** O(|E|) to store the set of expressible numbers, where `|E|` is the total number of expressible values, which can be very large.
**Pros:** More efficient than the full brute-force approach.; Correctly computes the set of all expressible numbers.
**Cons:** The number of expressible values can be very large, leading to high time and space complexity.; Will still time out or run out of memory for many test cases within the given constraints.
### Explanation
This method computes the closure of the initial set of numbers under the bitwise OR operation. We can use a worklist (a queue) to manage this process. We start by adding all unique numbers from `nums` to a set of `expressible` numbers and to the `worklist`. Then, we repeatedly extract a number from the `worklist` and OR it with every unique number from the original input. If a new number is generated that we haven't seen before, we add it to both the `expressible` set and the `worklist`. This ensures we explore all combinations. The process stops when the `worklist` is empty, meaning no new numbers can be formed. Finally, we check for the smallest missing positive integer.

```java
import java.util.HashSet;
import java.util.Set;
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int minImpossibleOR(int[] nums) {
        Set<Integer> uniqueNums = new HashSet<>();
        for (int num : nums) {
            uniqueNums.add(num);
        }

        Set<Integer> expressible = new HashSet<>(uniqueNums);
        Queue<Integer> worklist = new LinkedList<>(uniqueNums);

        while (!worklist.isEmpty()) {
            int current = worklist.poll();
            for (int num : uniqueNums) {
                int newOr = current | num;
                if (expressible.add(newOr)) {
                    worklist.add(newOr);
                }
            }
        }

        int missingNumber = 1;
        while (expressible.contains(missingNumber)) {
            missingNumber++;
        }
        return missingNumber;
    }
}
```
### Algorithm
- Create a `HashSet` `expressible` and a `Queue` `worklist`.
- Add all unique numbers from `nums` to both `expressible` and `worklist`.
- While `worklist` is not empty:
    - Dequeue a number `current`.
    - For each unique number `num` from the input:
        - Calculate `newOr = current | num`.
        - If `newOr` is not in `expressible`, add it to `expressible` and enqueue it to `worklist`.
- After the loop, check integers `i = 1, 2, 3, ...` and return the first `i` not in `expressible`.

## Greedy Power-of-Two Checking
This efficient approach is based on a key observation about how expressible numbers are formed. The smallest positive integer that is not expressible must be a power of two. The logic is as follows: if we can express all numbers from 1 to `2^k - 1`, to be able to express numbers beyond this range (specifically `2^k` and above), we need to be able to express `2^k`. The number `2^k` can only be expressed if `2^k` itself is present in `nums`. Therefore, we can find the answer by checking for powers of two (`1, 2, 4, 8, ...`) in increasing order. The first power of two that is not present in `nums` is the minimum impossible OR.
**Time:** O(N), where N is the number of elements in `nums`. Building the set takes O(N). The `while` loop runs at most `log(M)` times, where `M` is the maximum value in `nums` (approx. 30 times), which is negligible. The total time is dominated by set creation. · **Space:** O(U), where `U` is the number of unique elements in `nums`. In the worst case, this is O(N).
**Pros:** Highly efficient with linear time complexity.; Simple to implement.; Optimal solution for the given constraints.
**Cons:** The correctness relies on a non-trivial insight about bitwise OR and powers of two.
### Explanation
The core idea relies on this property: If all powers of two `1, 2, 4, ..., 2^(k-1)` are present in `nums`, then any integer from `1` to `2^k - 1` can be expressed. This is because any such integer can be represented as a sum of distinct powers of two (its binary representation), and we can form this number by a bitwise OR of the corresponding powers of two from `nums`.

Let `p = 2^k` be the smallest power of two that is *not* in `nums`. This implies that `1, 2, 4, ..., 2^(k-1)` are all present in `nums`. Based on the property, we can express all integers from `1` to `p - 1`. To express `p` itself, the bitwise OR of a subsequence must equal `p`. This is only possible if `p` is in the subsequence, but we know it is not in `nums`. Therefore, `p` is not expressible, and since all smaller integers are, `p` is the answer.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minImpossibleOR(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int powerOfTwo = 1;
        while (numSet.contains(powerOfTwo)) {
            powerOfTwo *= 2;
        }
        return powerOfTwo;
    }
}
```
### Algorithm
- Put all numbers from `nums` into a `HashSet` for efficient `O(1)` average time lookups.
- Initialize a variable `powerOfTwo` to 1.
- Loop while `powerOfTwo` is found in the set.
- Inside the loop, double `powerOfTwo`: `powerOfTwo *= 2`.
- When the loop terminates, `powerOfTwo` is the smallest power of two not in the set. Return `powerOfTwo`.

# Solutions
### Java

```java
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;
      }
    }
  }
}

```

### CPP

```cpp
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;
      }
    }
  }
};

```

### Python

```python
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)

```