Abstract / Summary

Find the xor of numbers that appear exactly two times in an array.

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 79% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Bit Manipulation
• Hash Table

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 single method duplicateNumbersXOR that receives a list of integers and returns an integer computed by applying the XOR (exclusive-or) operation in two stages. First, it reduces the entire input list with XOR, producing the cumulative XOR of all elements. Second, it reduces the set derived from the list-thereby removing duplicate occurrences-with XOR, producing the cumulative XOR of each distinct value exactly once. The final result is obtained by XOR-ing these two intermediate values. This approach leverages the mathematical properties of XOR to isolate the contribution of numbers that appear an even number of times in the original collection.

Key Steps

Step 1 - Reduce the full list with XOR

total_xor = reduce(xor, nums)

The reduce function iteratively applies the xor operator from the operator module to every element of nums. The associative nature of XOR ensures that the order of evaluation does not affect the final value. The resulting total_xor represents the parity-aware aggregation of all input numbers: each value that occurs an odd number of times contributes its value, while values occurring an even number of times cancel out to zero.

Step 2 - Reduce the set of unique numbers with XOR

unique_xor = reduce(xor, set(nums))

By converting nums to a set, the code discards duplicate occurrences, leaving exactly one instance of each distinct integer. Reducing this set with XOR yields unique_xor, which is simply the XOR of every distinct value present in the original list, regardless of how many times each appeared.

Step 3 - Combine the two intermediate results

result = total_xor ^ unique_xor

The final XOR between total_xor and unique_xor exploits the cancellation property of XOR. For any integer e that appears k times in nums:

• If k is odd, e contributes to total_xor and also appears in unique_xor; the two contributions cancel (e ^ e = 0).
• If k is even, e does not affect total_xor (even count yields zero) but does appear in unique_xor; the net contribution is e.

Consequently, the method returns the XOR of all numbers that occur an even number of times in the input list.

Edge Cases Handled

When the input list is empty, reduce receives an empty iterable. In Python, reduce without an explicit initializer raises a TypeError. However, the typical usage pattern for this algorithm supplies a non-empty list, and the surrounding problem context usually guarantees at least one element. If an empty list were passed, the conversion to a set also yields an empty set, leading to the same situation for the second reduce.

If the list contains only unique values, each element appears exactly once (odd count). The first reduction yields the XOR of all elements, while the second reduction yields the same XOR because the set is identical to the list. Their XOR cancels to zero, correctly indicating that no number appears an even number of times.

When every element appears an even number of times (for example, each value appears twice), the first reduction results in zero because each pair cancels out. The second reduction, however, retains one copy of each distinct value, so the final XOR equals the XOR of all distinct numbers, which matches the intended outcome.

The algorithm also gracefully handles large integer values and negative numbers because the XOR operator works uniformly across the full range of Python's arbitrary-precision integers.

Performance Optimizations

The implementation relies on built-in functions (reduce, xor, set) that are implemented in C, providing fast low-level execution compared to a pure Python loop. Converting the list to a set is performed once, avoiding repeated membership checks. The use of reduce eliminates the need for explicit indexing or manual accumulation, reducing Python bytecode overhead. By performing only two linear passes-one over the original list and one over the set of unique elements-the method achieves optimal traversal without auxiliary data structures beyond the set itself. This design minimizes memory churn and leverages the highly optimized hash table implementation underlying Python sets.

Imagine you have a big box of sparkling toy blocks. Most of the blocks are unique, but there are a couple of pairs that look exactly the same. The goal here is to find the blocks that have a match.

This code acts like a clever machine. First, it takes all the blocks you have in your box and does a special kind of magic math with them that combines their hidden values together. Then, it looks at the box again but only picks one of each kind of block, leaving the duplicates behind, and does that same magic math.

When it finishes, it compares the two results. Because most of the blocks cancelled each other out during the first step, only the ones that were hiding as duplicates are left standing at the end. It is like finding the secret twin blocks just by grouping them all together.

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	Java	C++		Python	TS
	WalkCCC	Java	C++		Python
	leetcode.ca	Java	C++	Go	Python	TS
	Progiez	Java	C++		Python
github	charles-wangkai	Java
	fsq		C++
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
varunu28	Java

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