LeetCode 2568 - Minimum Impossible OR

The problem asks us to find the smallest positive integer that cannot be represented as a bitwise OR of any subsequence of a given array nums. The input array contains positive integers, and the subsequences can have any length, including length 1.

leetcodemediumarraybit-manipulationbrainteaser

LeetCode Problem 2568

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation, Brainteaser

Solution

Problem Understanding

The problem asks us to find the smallest positive integer that cannot be represented as a bitwise OR of any subsequence of a given array nums. The input array contains positive integers, and the subsequences can have any length, including length 1. The output must be the smallest integer greater than zero that cannot be formed using the OR operation over these subsequences.

Bitwise OR is inclusive in the sense that it accumulates all bits set across numbers in a sequence. For example, if a number has its 1st and 3rd bits set and another number has the 2nd bit set, the OR will combine them, setting all three bits. The challenge lies in efficiently identifying the first positive integer that cannot be obtained from such combinations, especially since nums can have up to 10^5 elements, and each element can be as large as 10^9.

Key observations include that this is fundamentally a problem about powers of two because each integer is representable in binary, and OR-ing subsets tends to generate sums of powers of two. Edge cases to watch for include arrays that are missing 1 entirely (in which case 1 is immediately the answer) and arrays where elements form consecutive powers of two with gaps.

Approaches

Brute Force

A brute-force approach would enumerate all subsequences of nums, calculate their OR values, and track which integers are expressible. Once all OR values are collected, we would check incrementally from 1 upwards for the first missing integer. While correct in principle, this method is computationally infeasible because the number of subsequences of an array of length n is 2^n, which is exponential. This is far too slow for n up to 10^5.

Optimal Approach

The key insight is to recognize that the minimum impossible OR always corresponds to a power of two that is missing in the array. We can maintain a set of numbers and iterate over powers of two, starting from 1, doubling each time. If a power of two is not present in the array, that power is the minimum impossible OR. This works because OR-ing smaller numbers can only generate numbers up to the sum of smaller powers of two. The first missing power of two cannot be reached by OR-ing any combination of smaller numbers, making it the correct answer.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(2^n) Enumerate all subsequences and their ORs, infeasible for large n
Optimal O(n) O(log(max(nums))) Track powers of two, check smallest missing, feasible for n up to 10^5

Algorithm Walkthrough

  1. Initialize a variable power to 1. This represents the current power of two we are checking.
  2. Create a set num_set from the array nums to allow O(1) lookups for numbers.
  3. Enter a loop where we check if power exists in num_set.
  4. If power exists, multiply power by 2 and repeat. This checks the next power of two.
  5. If power does not exist in the set, return power immediately as the minimum impossible OR.

Why it works: Because each power of two is the fundamental building block in binary representation, any number expressible as ORs of existing numbers must be some combination of the powers of two already in the array. The first missing power of two cannot be formed by OR-ing smaller powers, so it is guaranteed to be the smallest non-expressible integer.

Python Solution

from typing import List

class Solution:
    def minImpossibleOR(self, nums: List[int]) -> int:
        num_set = set(nums)
        power = 1
        while power in num_set:
            power <<= 1
        return power

This solution converts the list into a set for O(1) membership checks. It then iterates through powers of two using bit shifting until it finds one that is not in the set, which it immediately returns.

Go Solution

func minImpossibleOR(nums []int) int {
    numSet := make(map[int]struct{})
    for _, num := range nums {
        numSet[num] = struct{}{}
    }
    power := 1
    for {
        if _, exists := numSet[power]; !exists {
            return power
        }
        power <<= 1
    }
}

In Go, we use a map with empty struct values to represent the set. Membership checking is similar, and we iterate through powers of two using left shift until the missing power is found.

Worked Examples

Example 1: nums = [2,1]

Step power num_set contains power? Action
1 1 Yes power <<= 1 -> power = 2
2 2 Yes power <<= 1 -> power = 4
3 4 No Return 4

Result: 4

Example 2: nums = [5,3,2]

Step power num_set contains power? Action
1 1 No Return 1

Result: 1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Constructing the set takes O(n), iterating through powers of two takes at most O(log(max(nums))) which is negligible relative to n
Space O(n) The set stores all numbers from nums

The algorithm is efficient because it only requires a single pass to build the set and a logarithmic number of checks relative to the maximum number.

Test Cases

# Provided examples
assert Solution().minImpossibleOR([2,1]) == 4  # minimal missing OR is 4
assert Solution().minImpossibleOR([5,3,2]) == 1  # minimal missing OR is 1

# Edge cases
assert Solution().minImpossibleOR([1,2,4,8]) == 16  # consecutive powers of two
assert Solution().minImpossibleOR([1]) == 2  # single element
assert Solution().minImpossibleOR([2]) == 1  # missing smallest power of two
assert Solution().minImpossibleOR([3,7,15]) == 1  # all numbers missing 1
assert Solution().minImpossibleOR([1,3,5,7]) == 2  # 2 missing
Test Why
[2,1] Simple small array, missing 4
[5,3,2] Missing 1, smallest number not in array
[1,2,4,8] Consecutive powers of two, missing next power 16
[1] Single element, minimal positive missing 2
[2] Single element, missing smallest power 1
[3,7,15] All numbers missing 1, OR combinations cannot generate 1
[1,3,5,7] Non-consecutive numbers, missing power 2

Edge Cases

The first edge case is when nums does not contain 1. Since 1 is the smallest positive integer, the answer is immediately 1. This is a common edge case that could be missed if the algorithm blindly checks higher numbers first.

The second edge case is when nums contains consecutive powers of two. In this case, the algorithm must correctly identify the next missing power beyond the largest present, not assume all integers in between are representable.

The third edge case is arrays containing only odd numbers greater than 1. None of these numbers can produce the OR value 1, so the algorithm must correctly identify that 1 is missing, which validates the use of powers of two logic.

This approach systematically handles these edge cases because it checks incrementally from the smallest power of two and returns the first missing one.