Abstract / Summary

Compute the bitwise XOR of the bitwise AND of every unique pair of numbers in the given list.

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 63% (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 Solution class with a single method getXORSum. The method receives two integer lists, arr1 and arr2, and returns an integer that is the result of a three-stage bitwise computation. First, it reduces arr1 to a single XOR value. Second, it applies a bitwise AND between that XOR value and each element of arr2. Finally, it reduces the resulting sequence with XOR again to produce the answer. The code relies on the functional utilities reduce and map from Python’s standard library, together with the xor operator from the operator module.

Step 1: Compute XOR of the first array

one = reduce(xor, arr1)

In this line the reduce function iteratively applies the xor operation across all elements of arr1. The cumulative effect is that one holds the bitwise XOR of every integer in the first list. If arr1 is empty, reduce would raise an exception, but the surrounding context (the problem constraints) guarantees a non-empty input, so the code safely obtains a deterministic value.

Step 2: Mask each element of the second array

two = map(lambda x: x & one, arr2)

Here a map object is created by applying a lambda that performs a bitwise AND between each element x of arr2 and the previously computed one. The AND operation zeroes out any bits in x that are not present in one, effectively filtering arr2 through the bit pattern derived from arr1. The use of map yields a lazy iterator, meaning the actual computation for each element is deferred until the iterator is consumed.

Step 3: Aggregate final XOR

return reduce(xor, two)

The final line consumes the two iterator, applying XOR across all masked values. The result of this reduction is the method’s return value. Because two is an iterator, the XOR reduction processes each element exactly once, without materializing an intermediate list.

Edge Cases Handled

The algorithm inherently accommodates several edge conditions:

• When arr1 contains a single element, the first reduction simply returns that element, and the subsequent AND operation uses it directly as a mask.
• If all elements of arr1 XOR to zero, the mask one becomes zero. Consequently, every element of arr2 is ANDed with zero, producing a sequence of zeros; the final XOR of zeros yields zero, which is the mathematically correct outcome.
• When arr2 contains a single element, the map produces a single masked value, and the final reduction returns that value unchanged, matching the expected behavior for a solitary operand.
• The code gracefully handles duplicate values in either list because XOR is associative and commutative; duplicate contributions cancel out when they appear an even number of times, which is reflected automatically by the reductions.

Performance Optimizations

The implementation leverages functional primitives that are implemented in C, offering speed advantages over equivalent pure-Python loops. The use of reduce for the XOR aggregations avoids the overhead of explicit iteration and temporary variables. Moreover, the map construct creates a lazy iterator, preventing the allocation of an intermediate list that would otherwise double memory usage for large inputs. This laziness also enables the final reduce to consume elements on the fly, maintaining a low memory footprint throughout the computation. The overall flow processes each element of both input lists exactly once, ensuring that the algorithm scales linearly with the total number of elements.

Imagine there are two boxes filled with special number marbles. The goal is to mix these marbles in a very specific way to find a secret key. First, all the marbles in the first box are combined using a math trick called XOR that snaps them together into a single new marble. Next, that new marble is taken and used to change every single marble in the second box by using another math trick called AND, which acts like a filter to keep only parts of the numbers that match. Finally, all those changed marbles from the second box are snapped together using the XOR trick one last time until only one final marble remains.

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	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	haoel	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	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