Abstract / Summary

Given two arrays, find the smallest possible result of xor-ing each pair and summing those results by choosing how to pair elements.

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

Typical patterns to solve this problem:

• Array
• Bit Manipulation
• Bitmask
• Dynamic Programming

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 solves the problem of pairing two equally-sized integer arrays so that the sum of pairwise XOR values is minimized. It treats the task as a permutation search: each element of nums1 must be matched with a distinct element of nums2. The core of the solution is a depth-first search that explores all possible assignments while memoizing intermediate results to avoid redundant work.

Core Logic

Size Determination

size = len(nums1)          # == len(nums2)

The algorithm begins by recording the common length of the two input lists. This value drives the recursion depth and the size of the bitmask used to track assignments.

Recursive Function with Memoization

@cache
def deeper(pos, have):
    if pos == size:
        return 0
    ...

The inner function deeper receives two parameters: pos, the current index in nums1 that is being paired, and have, a bitmask indicating which positions in nums2 have already been used. The @cache decorator (from functools) automatically stores the result of each unique (pos, have) combination, turning the exponential search into a tractable dynamic programming solution.

Base Case

if pos == size:
    return 0

When every element of nums1 has been assigned (pos reaches size), the recursion terminates and contributes zero to the accumulated sum. This base case also implicitly handles the edge condition where both input lists are empty; the function returns 0 without entering the loop.

Exploration of Unassigned Elements

best = +inf
for i in range(size):
    mask = 1 << i
    if have & mask:          # already done
        continue
    xor = nums1[pos] ^ nums2[i]
    best = min(best, xor + deeper(pos + 1, have ^ mask))

The loop iterates over every index i of nums2. The expression mask = 1 << i creates a single-bit flag for the current position. The condition have & mask checks whether this flag is already set, meaning the element has been paired earlier; if so, the iteration skips to the next candidate.

When an unused element is found, the XOR of the current pair is computed. The recursive call advances to the next position in nums1 (pos + 1) and updates the bitmask with have ^ mask. Because mask was not set before, the XOR operation effectively adds the bit to the mask, mirroring a logical OR. The sum of the current XOR and the optimal remainder (deeper(...)) is compared against the running minimum best.

Final Result

return deeper(0, 0)

The outermost call starts the recursion with the first element of nums1 (pos = 0) and an empty assignment mask (have = 0). The returned value is the minimal possible total XOR sum.

Edge Cases Handled

The algorithm gracefully manages several boundary conditions without explicit checks. When the input lists are empty, size becomes 0, the initial call to deeper immediately satisfies the base case, and the function returns 0. Duplicate values in either list do not affect correctness because each position is distinguished by its index, and the bitmask ensures that each element of nums2 is used exactly once. The use of a bitmask also prevents out-of-range errors, as the mask is constructed only for indices within the known size.

Performance Optimizations

The most significant optimization is the memoization provided by the @cache decorator. By caching the result of each (pos, have) state, the algorithm avoids recomputing the same subproblem multiple times, effectively converting the naïve exponential enumeration into a dynamic programming approach whose state space is bounded by size * 2^size.

Representing the set of already assigned indices as an integer bitmask yields constant-time checks (have & mask) and updates (have ^ mask). This compact representation reduces memory overhead compared to alternative structures such as lists or sets, and it enables fast bitwise operations that are native to the processor.

The loop iterates only over indices that have not yet been assigned, thanks to the early continue when have & mask is true. This pruning eliminates unnecessary recursive calls and keeps the search focused on viable permutations.

Overall, the combination of depth-first exploration, bitmask state encoding, and automatic caching delivers an efficient solution for the combinatorial pairing problem.

Imagine you have two rows of toy boxes. Each box has a number written on it. The goal is to pick one box from the first row and one box from the second row to make pairs until every box has a partner. When you pair two numbers, there is a special magic trick called xor that combines them into a brand new value. The goal is to make all those magic values as small as possible when you add them all up.

The code starts by looking at the first number in the top row. It tries pairing that number with every single box in the bottom row one by one. To keep track of which boxes in the bottom row have already been chosen, the program uses a tiny digital checklist called a mask. Think of it like putting a sticker on a box so you know it is taken.

Once a pair is made, the program moves on to the next number in the top row and repeats the process. Because there are many ways to pair the boxes, the computer remembers the best score it has found so far for each situation. This helps it skip repeating work it already finished. If the program sees it has reached the very last box, it knows it is finished and finishes the job. This method looks at every possible combination of pairs to find the special way that makes the total magic value the smallest one possible.

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

Time: exponential
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++
	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++
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