Abstract / Summary

Given a list of numbers you can replace any number by its xor with another from the list any number of times find the highest xor value possible.

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 80% (40k+ submissions).

Typical patterns to solve this problem:

• Array
• Bit Manipulation
• Math

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 single method maximumXOR. The method receives a list of non-negative integers and returns the largest possible XOR value that can be obtained by selecting a subset of the numbers and XOR-ing them together. The algorithm works by examining the binary representation of each input number, counting how many times each bit position is set, and then constructing the result from the bits that appear at least once.

Key Steps

The first important step is the definition of the maximum bit index that the algorithm will examine. The constant maxBit is set to 27 because the problem constraints guarantee that the numbers do not exceed (10^8), whose binary length is at most 27 bits.

maxBit = 27  # log2(10**8) is about 26.5

Next, the code creates an array named all with a length equal to maxBit. This array holds the count of how many input numbers have the corresponding bit set.

all = [0] * maxBit

The algorithm then iterates over each number in the input list. For each number it checks every bit position from 0 up to maxBit-1. If the bit is set, the corresponding counter in all is incremented.

for n in nums:
    for i in range(maxBit):
        if n & (1 << i):
            all[i] += 1

After the counting phase, the method builds the final answer. It starts with a result value of zero and walks through the all array. Whenever a counter is greater than zero, the algorithm sets the same bit in the result. This effectively creates a number whose binary representation contains every bit that appears in any of the input numbers.

result = 0
for i in range(maxBit):
    if all[i] > 0:
        result |= 1 << i

Finally, the computed result is returned to the caller.

return result

Edge Cases Handled

The algorithm gracefully handles the situation where the input list is empty. In that case the outer loop that counts bits never executes, leaving the all array filled with zeros. The subsequent construction of result never sets any bit, so the method returns zero, which is the correct maximum XOR for an empty set.

When all numbers in the list are zero, each bit test n & (1 << i) evaluates to false for every iteration, leaving all counters at zero. The result construction again produces zero, matching the expected outcome because XOR of any combination of zeros remains zero.

If the input contains duplicate values, the counting phase simply increments the counters for each occurrence. The final result depends only on whether a bit appears at least once, not on how many times it appears, so duplicates do not affect the correctness of the answer.

The code also works correctly when the input contains the maximum allowed value (close to (10^8)). The maxBit limit of 27 ensures that all relevant bits are examined, and any higher bits are ignored because they are guaranteed to be zero for the given constraints.

Performance Optimizations

The implementation avoids the need for nested data structures by using a flat list all to store bit counts. This choice reduces memory overhead and enables fast index-based updates.

The inner loop that checks each bit uses a bitwise AND operation combined with a left shift (n & (1 << i)). This operation is highly efficient on modern CPUs and eliminates the need for more expensive arithmetic or string conversions.

By pre-computing the maximum bit length (maxBit) based on the problem constraints, the algorithm limits the number of iterations in both the counting and result-building phases. This prevents unnecessary work on higher bit positions that can never be set.

The final construction of the result uses the bitwise OR assignment (result |= 1 << i) only when a bit has been observed. This conditional update avoids redundant writes to the result variable for bits that remain zero.

Overall, the code follows a linear scan of the input list combined with a fixed-size inner loop, delivering a solution that scales directly with the size of the input while keeping per-element work bounded by a small constant.

Imagine you have a big treasure chest filled with lots of number blocks. Each block has little light switches on it that can be either on or off, standing for zeros and ones. The goal here is to find the biggest possible number you can make by combining these blocks in a special way.

First, the code looks at every single number block you have. It goes through each of the twenty-seven light switches on every block one by one. It keeps a tally of how many blocks have the switch turned on for each position. It creates a list called all to remember these counts.

After checking every block, it looks at the final list to see which switch positions had at least one block turned on. If a position has even one switch flipped up, that means it is possible to include that piece in the final big result.

Finally, it builds the biggest number by adding all those pieces together. It starts with a zero and, for every position where it found at least one switch turned on, it flips the corresponding switch in the final result. By the time it finishes, it has created a brand new number that represents the most light switches possible being turned on.

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		Python	Java	C++		TS
	WalkCCC		Python	Java	C++
	leetcode.ca		Python	Java	C++	Go	TS
	Progiez		Python	Java	C++
github	charles-wangkai			Java
	everthis	JS
	fsq				C++
	JoshCrozier	JS
	lkwq007		Python
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

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