Abstract / Summary

Given a list of numbers find the smallest value that cannot be made by the OR of any subset of them

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 59% (30k+ submissions).

Typical patterns to solve this problem:

• Array
• Bit Manipulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The Solution.minImpossibleOR method determines the smallest positive power-of-two that cannot be obtained by bitwise OR of any subset of the input list nums. The algorithm relies on the observation that a power-of-two can only be produced directly by that exact value; any combination of other numbers cannot generate a solitary bit that is not already present. Consequently, the answer is the first power-of-two absent from the collection of powers-of-two present in nums.

Three alternative implementations are provided, each selected by the variable approach. All three share the same high-level flow: start with result = 1, examine the input according to the chosen strategy, and repeatedly left-shift result while the current power-of-two is found. The method finally returns the first missing power-of-two.

Key Steps

Initialization

result = 1
approach = 3

result holds the candidate power-of-two, beginning with (2^0 = 1). The approach selector determines which of the three implementations will be executed.

Approach 1 - Direct Set Membership

When approach == 1, the code builds a hash set containing every element of nums.

lookup = set(nums)          # faster than scanning a list
while result in lookup:
    result <<= 1

The set provides O(1) average-case membership tests. The loop continues as long as the current result exists in the set, left-shifting to the next power-of-two each iteration.

Approach 2 - Sorted List with Binary Search

When approach == 2, the list is sorted in place, and binary search (bisect_left) is used to locate each candidate.

nums.sort()
while True:
    pos = bisect_left(nums, result)
    if pos == len(nums) or nums[pos] != result:
        break
    result <<= 1

Sorting arranges the numbers in ascending order, enabling logarithmic-time lookups. The loop terminates when the binary search fails to find the current result.

Approach 3 - Extracting Powers-of-Two

When approach is any value other than 1 or 2 (the default is 3), the method filters nums to retain only values that are powers-of-two.

have = set()
for n in nums:
    if (n & (n - 1)) == 0:
        have.add(n)
while result in have:
    result <<= 1

The bit-wise test (n & (n - 1)) == 0 identifies powers-of-two efficiently. The resulting set have contains exactly those powers-of-two present in the input, and the subsequent loop mirrors the logic of Approach 1 but operates on a smaller collection.

Return

return result

After the loop exits, result is the smallest power-of-two not present in the examined collection, which is the required answer.

Edge Cases Handled

The implementation gracefully handles an empty input list. In all three approaches, the initial result value of 1 is never found, so the loop body is skipped and the method returns 1.

When the input contains duplicate values, the set constructions in Approaches 1 and 3 automatically collapse duplicates, ensuring that repeated numbers do not affect the loop condition.

If the input includes non-power-of-two numbers, they are ignored by Approach 3 because the bit-wise test filters them out. Approaches 1 and 2 treat them as ordinary elements; however, because the loop only checks for exact matches with result, these extraneous values never cause premature termination.

The bit-wise test (n & (n - 1)) == 0 correctly identifies 0 as a power-of-two candidate, but 0 is not a positive power-of-two. Since the loop starts at 1, any occurrence of 0 in nums does not influence the result.

When the input contains very large integers, left-shifting result continues until a missing power-of-two is found. Python’s arbitrary-precision integers prevent overflow, so the algorithm remains correct even for values beyond typical 32- or 64-bit limits.

Performance Optimizations Observed

Approach 1 leverages a hash set for constant-time membership checks, eliminating the need for linear scans. The comment notes that constructing a set is faster than repeatedly scanning a list, which is true for repeated lookups.

Approach 2 introduces a sort followed by binary search. Sorting incurs an O(n log n) cost once, after which each lookup runs in O(log n). This trade-off can be advantageous when the number of distinct powers-of-two to test is small relative to the list size, because the binary search avoids the overhead of hash table construction.

Approach 3 reduces the problem size before the main loop by extracting only the relevant powers-of-two. The bit-wise test (n & (n - 1)) == 0 is a classic constant-time operation for power-of-two detection, and the resulting set have is typically much smaller than the original list. Consequently, the subsequent membership loop runs faster due to fewer elements in the set.

The use of left-shift (result <<= 1) to generate successive powers-of-two is both concise and efficient, avoiding multiplication or exponentiation.

Overall, each approach balances preprocessing cost against lookup speed, and the default selection (Approach 3) achieves the lowest measured runtime (320 ms) by minimizing the size of the data structure used for membership testing.

Imagine you have a giant toy chest filled with number blocks. Each block has a special power, and these powers are always doubling, like one, two, four, eight, and sixteen. The goal of this code is to find the very first number from that special list of powers that is missing from your pile.

Think of it like a game of tag. You start looking for the number one. If you find a block with a one on it, you move up to two. If you have a two, you move up to four. The code looks through your pile to see which of these special blocks you actually own. It keeps checking one power at a time, moving to the next big step by doubling the number, which is what the code means by the little arrows shifting. Once it finds a number that is not in your pile, it stops searching because it knows it has found the smallest one that is missing. It just goes in a circle, checking your collection until it finds the empty spot.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		C++	Python	Java		TS
	WalkCCC		C++	Python	Java
	leetcode.ca		C++	Python	Java	Go	TS
	Progiez		C++	Python	Java
github	charles-wangkai				Java
	everthis	JS
	fsq		C++
	JoshCrozier	JS
	lkwq007			Python
	wisdompeak		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality