Abstract / Summary

Find a continuous part of the array where the bitwise OR of its elements is closest to a given number.

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 31% (50k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Bit Manipulation
• Segment Tree

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 provided implementation defines a class Solution with a method minimumDifference that computes the smallest absolute difference between a target value k and the bitwise-OR of any contiguous subarray of the input list nums. The algorithm iterates through the array while maintaining a compact representation of reachable OR values that are still candidates for improving the result. Throughout the traversal it updates the best distance found and discards values that can no longer contribute to a smaller difference.

Initialization

At the start of the method two variables are prepared.

result = +inf
have = []

result holds the best (smallest) absolute difference discovered so far and is initialized to positive infinity so that any real difference will replace it. have is an empty list that will store the OR values of subarrays ending at the previously processed element, kept in increasing order and without duplicates.

Processing each element

The core of the algorithm is a loop that examines each integer n from nums.

for n in nums:
    result = min(result, abs(n - k))

The first operation treats the single-element subarray consisting of n alone, updating result with the distance between n and k. This handles the edge case where the optimal subarray has length one, ensuring that the algorithm never overlooks a trivial solution.

Extending existing subarrays

For every previously stored OR value h the algorithm computes the OR with the current element n.

next = []
for h in have:
    more = h | n
    if more < k:
        if not next or next[-1] != more:
            next.append(more)
    else:
        result = min(result, more - k)

If the new OR more remains below the target k, it is a candidate for future extensions and is appended to a temporary list next. The condition next[-1] != more guarantees that duplicate values are not stored, preserving the monotonic nature of the list. When more reaches or exceeds k, the algorithm knows that any further OR operations will only increase the value (because OR is monotonic). Consequently it immediately updates result with the excess more - k and refrains from adding more to next. This early termination for oversized values is a key optimization that prevents unnecessary growth of the candidate set.

Comparing with the largest smaller value

After processing all prior ORs, the algorithm may have a non-empty next list containing values strictly less than k. The largest of these values is the last element because the list is kept sorted.

if next:
    result = min(result, k - next[-1])

By measuring the gap k - next[-1], the method captures the best possible improvement from any subarray that ends at the current position and stays below k. This step handles the edge case where the optimal subarray yields an OR just under the target, ensuring that the algorithm does not miss a close-but-under solution.

Inserting the current element as a new subarray

The current number n can also start a new subarray. If it is smaller than k, it is inserted into next while preserving order.

if n < k:
    insort(next, n)

The use of insort (binary insertion) maintains the sorted invariant of next without a full resort, which is a performance optimization that keeps insertion cost logarithmic relative to the size of the list.

Updating the candidate set

Finally, the temporary list next becomes the new set of OR values for the next iteration.

have = next

By replacing have with next, the algorithm discards any OR values that have already been proven incapable of improving the result, thereby limiting the size of the stored state.

Edge-case handling

The code explicitly addresses several boundary conditions. When nums contains a single element, the initial update result = min(result, abs(n - k)) yields the correct answer without entering the inner loop. If all OR values generated are greater than or equal to k, the branch that updates result with more - k ensures that the smallest excess is recorded. Conversely, when all generated ORs stay below k, the comparison with k - next[-1] captures the closest approach from below. The duplicate-avoidance check (next[-1] != more) prevents redundant entries that could otherwise cause unnecessary work in later iterations.

Performance optimizations

The algorithm leverages the monotonic property of the bitwise-OR operation: once an OR value reaches or exceeds k, any further OR with additional numbers cannot reduce it. By pruning such values immediately, the method keeps the candidate list short. The sorted nature of have and next enables binary insertion via insort, avoiding linear scans for placement. Duplicate elimination further reduces the number of elements that need to be processed in subsequent loops. Together, these tactics limit the amount of work performed per array element and avoid exponential blow-up that a naïve enumeration of all subarrays would incur.

Imagine a row of building blocks, each with a different number painted on it. The goal is to pick a group of blocks that are sitting right next to each other and combine them in a special way. When blocks are combined, they mix their numbers together like colors in a paint set.

The code starts by looking at every block one by one to see how close its number gets to a target number. It keeps a list of all the different combinations it has seen so far. For every new block, it mixes that block with all the previous combinations.

If a mix becomes larger than the target, the code checks to see how far away it is and writes that down if it is the closest one found yet. If a mix stays smaller than the target, that mix is saved in the list to be used again with the next block. By doing this over and over, the code keeps track of all the possible mixes and finds the one that lands closest to the target number.

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

not analyzed yet

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++			Java	Python	TS
	WalkCCC	C++			Java	Python
	leetcode.ca	C++		Go	Java	Python	TS
	Progiez	C++			Java	Python
github	everthis		JS
	fsq	C++
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
everthis	JavaScript
fsq	C++
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