Minimum Impossible OR
MedPrompt
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 <= 1051 <= nums[i] <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize an empty
HashSetcalledexpressibleNumbers. - Generate all
2^N - 1non-empty subsequences ofnumsusing a bitmask from1to(1 << N) - 1. - For each subsequence:
- Calculate the bitwise OR of all its elements, let the result be
orValue. - Add
orValueto theexpressibleNumbersset.
- Calculate the bitwise OR of all its elements, let the result be
- Initialize a variable
missingNumberto 1. - Loop indefinitely:
- If
missingNumberis not inexpressibleNumbers, return it. - Otherwise, increment
missingNumber.
- If
Walkthrough
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.
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++; } }}Complexity
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.
Trade-offs
Pros
Conceptually simple and directly follows the problem statement.
Cons
Extremely inefficient due to its exponential time complexity.
Not feasible for the given constraints (
Nup to 10^5).Will result in Time Limit Exceeded and Memory Limit Exceeded for large inputs.
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.
Algorithm
- Create a
HashSetexpressibleand aQueueworklist. - Add all unique numbers from
numsto bothexpressibleandworklist. - While
worklistis not empty:- Dequeue a number
current. - For each unique number
numfrom the input:- Calculate
newOr = current | num. - If
newOris not inexpressible, add it toexpressibleand enqueue it toworklist.
- Calculate
- Dequeue a number
- After the loop, check integers
i = 1, 2, 3, ...and return the firstinot inexpressible.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Put all numbers from
numsinto aHashSetfor efficientO(1)average time lookups. - Initialize a variable
powerOfTwoto 1. - Loop while
powerOfTwois found in the set. - Inside the loop, double
powerOfTwo:powerOfTwo *= 2. - When the loop terminates,
powerOfTwois the smallest power of two not in the set. ReturnpowerOfTwo.
Walkthrough
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.
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; }}Complexity
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).
Trade-offs
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.
Solutions
Solution
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; } } }}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; } } }};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)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.