Problem Description

You are given a 0-indexed integer array nums.

An integer x is considered expressible from nums if you can select some elements from the array (in their original order) and combine them using the bitwise OR operation to get x. More formally, x is expressible if there exist indices 0 <= index₁ < index₂ < ... < indexₖ < nums.length such that nums[index₁] | nums[index₂] | ... | nums[indexₖ] = x.

Your task is to find the smallest positive integer that cannot be expressed using any subsequence of nums with the bitwise OR operation.

For example, if nums = [1, 2]:

• 1 is expressible (it's in the array)
• 2 is expressible (it's in the array)
• 3 is expressible (1 | 2 = 3)
• 4 is not expressible (cannot be formed by any OR combination)

The solution leverages the key insight that for any power of 2 (like 1, 2, 4, 8, etc.) to be expressible, it must exist directly in the array. This is because a power of 2 has only one bit set, and the OR operation can only turn bits on, never off. Therefore, the algorithm checks each power of 2 in increasing order (1, 2, 4, 8, ...) and returns the first one that doesn't appear in nums.

The code uses 1 << i to generate powers of 2 (which is equivalent to 2^i) and checks if each one exists in a set created from nums for O(1) lookup time.

Intuition

To understand why we only need to check powers of 2, let's think about how the bitwise OR operation works. The OR operation can only turn bits from 0 to 1, never from 1 to 0. This means we can only "add" bits to our result, never remove them.

Consider any power of 2, like 4 (which is 100 in binary). For 4 to be expressible through OR operations, we need at least one number in our subsequence that has the bit at position 2 set to 1. But here's the crucial insight: if we OR multiple numbers together and none of them have that specific bit set, we can never create it. Since 4 has only that single bit set and all other bits are 0, the only way to express 4 is if 4 itself appears in the array.

Now, what about non-powers of 2? Take 3 (which is 11 in binary). We can express 3 if we can express both 1 (01) and 2 (10), because 1 | 2 = 3. More generally, any integer can be broken down into a sum of distinct powers of 2 (its binary representation), and we can express it if we can express all those constituent powers of 2.

This leads us to the key realization: if all powers of 2 up to a certain point are expressible (exist in the array), then all positive integers up to their sum are also expressible. For instance:

• If we have 1, we can express 1
• If we have 1 and 2, we can express 1, 2, 3
• If we have 1, 2, and 4, we can express all integers from 1 to 7

Therefore, the smallest unexpressible positive integer must be the smallest power of 2 that doesn't appear in the array. We check 1, then 2, then 4, then 8, and so on, returning the first one we don't find.

Solution Approach

The implementation follows directly from our understanding that we need to find the smallest power of 2 that doesn't exist in the array.

Step 1: Convert array to set

s = set(nums)

We first convert the array nums into a set s for O(1) lookup time. This optimization is important because we'll be checking membership multiple times.

Step 2: Check powers of 2 in ascending order

return next(1 << i for i in range(32) if 1 << i not in s)

This line uses a generator expression with Python's next() function to find the first power of 2 that isn't in our set:

• i in range(32): We iterate through powers from 0 to 31. Since we're dealing with 32-bit integers (typical constraint in LeetCode problems), checking up to 2^31 is sufficient.

• 1 << i: This is a bit shift operation that efficiently calculates 2^i. For example:

  • 1 << 0 = 1 (binary: 1)
  • 1 << 1 = 2 (binary: 10)
  • 1 << 2 = 4 (binary: 100)
  • 1 << 3 = 8 (binary: 1000)

• if 1 << i not in s: This condition filters to only include powers of 2 that are NOT in our set.

• next(): Returns the first value from the generator that satisfies our condition.

Why this works: As established in our intuition, if we have all powers of 2 from 1 to 2^(k-1), we can express all integers from 1 to 2^k - 1 through OR operations. The moment we find a missing power of 2, that's our answer - it cannot be expressed through any OR combination of the available numbers.

Time Complexity: O(n) where n is the length of the input array (for creating the set) Space Complexity: O(n) for storing the set

Example Walkthrough

Let's walk through the solution with nums = [1, 2, 6, 8]:

Step 1: Convert to set for fast lookup

• Create set: s = {1, 2, 6, 8}

Step 2: Check powers of 2 in ascending order

Check 1 << 0 = 1:

• Is 1 in set? Yes ✓ (continue)

Check 1 << 1 = 2:

• Is 2 in set? Yes ✓ (continue)

Check 1 << 2 = 4:

• Is 4 in set? No ✗ (found our answer!)

Result: 4

Why is 4 the smallest unexpressible integer?

• We can express 1 (directly in array)
• We can express 2 (directly in array)
• We can express 3 (1 | 2 = 3)
• We cannot express 4 because:
  • 4 in binary is 100 (only bit 2 is set)
  • Our numbers in binary are:
    • 1 = 001
    • 2 = 010
    • 6 = 110
    • 8 = 1000
  • No combination of OR operations can create 100 since none of our numbers have ONLY bit 2 set
  • Any OR combination that includes 6 would give us 110 or higher (extra bits)
  • The number 8 has a different bit position set entirely

Therefore, 4 is the smallest positive integer that cannot be expressed.

Solution Implementation

Time and Space Complexity

The time complexity is O(n + log M), where n is the length of the array nums and M is the maximum value in the array nums.

• Creating the set s from nums takes O(n) time.
• The generator expression iterates through powers of 2 (i.e., 1 << i for i from 0 to 31). In the worst case, it checks up to 32 values, but since we're looking for the minimum impossible OR value, it will stop at the first power of 2 not in the set. The number of powers of 2 to check is bounded by O(log M) where M is the maximum value in nums, since any power of 2 greater than M cannot be formed by OR operations on elements ≤ M.
• Each membership check (1 << i not in s) takes O(1) average time for a set.
• Therefore, the total time complexity is O(n) + O(log M) × O(1) = O(n + log M).

The space complexity is O(n) because we create a set s that stores all unique elements from the input array nums, which in the worst case contains n distinct elements.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Attempting to Generate All Possible OR Combinations

The Wrong Approach: Many people's first instinct is to generate all possible OR combinations from the array and then find the smallest missing positive integer:

def minImpossibleOR(self, nums: List[int]) -> int:
    # WRONG: This tries to generate all possible OR values
    possible_values = set()
    n = len(nums)
  
    # Generate all subsequences and their OR values
    for mask in range(1, 1 << n):  # All non-empty subsequences
        or_value = 0
        for i in range(n):
            if mask & (1 << i):
                or_value |= nums[i]
        possible_values.add(or_value)
  
    # Find smallest missing positive integer
    result = 1
    while result in possible_values:
        result += 1
    return result

Why This Fails:

• Time complexity is O(2^n × n), which causes Time Limit Exceeded for large inputs
• The approach doesn't leverage the key insight about powers of 2
• It's unnecessarily complex for what the problem actually requires

Pitfall 2: Checking All Positive Integers Sequentially

The Wrong Approach:

def minImpossibleOR(self, nums: List[int]) -> int:
    # WRONG: Checking if each integer can be formed
    nums_set = set(nums)
  
    for candidate in range(1, max(nums) + 2):
        # Try to check if candidate can be formed by OR operations
        # This gets complicated and inefficient quickly
        can_form = False
        # ... complex logic to check if candidate is expressible ...
        if not can_form:
            return candidate

Why This Fails:

• Checking whether an arbitrary number can be formed through OR operations is complex
• The approach misses the fundamental property that powers of 2 are the limiting factor
• Could lead to incorrect results if the checking logic isn't perfectly implemented

Pitfall 3: Forgetting Edge Cases with Large Numbers

The Wrong Approach:

def minImpossibleOR(self, nums: List[int]) -> int:
    nums_set = set(nums)
  
    # WRONG: Only checking small range
    for i in range(20):  # Arbitrary small limit
        if (1 << i) not in nums_set:
            return 1 << i

Why This Fails:

• If the array contains all powers of 2 up to a large value, this could miss the answer
• Should check up to at least 30-31 bits for typical integer constraints

The Correct Solution Addresses These Pitfalls:

class Solution:
    def minImpossibleOR(self, nums: List[int]) -> int:
        nums_set = set(nums)
      
        # Check powers of 2 up to reasonable limit (32 bits)
        for i in range(32):
            power_of_two = 1 << i
            if power_of_two not in nums_set:
                return power_of_two

Key Insights to Remember:

1. Only powers of 2 matter for determining what cannot be expressed
2. Use set for O(1) lookups instead of repeated array searches
3. Check sufficient range (32 bits covers all standard integer values)
4. Keep the solution simple - don't overcomplicate with subsequence generation