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.
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; } } }}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.