What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 12 patterns and 201 archetypes is 100% free to access with no credit card required. Students receive 40 free compute coins upon registration, +20 daily login coins, and +25 referral coins. A 24-hour unlimited AI coaching pass costs only 5 coins. Alternatively, developers can use Bring-Your-Own-Key (BYOK) for completely free unlimited AI coaching with personal Gemini or OpenAI keys. There are no recurring subscription fees.

What is the refund and cancellation policy?

Hi👋SpeedAlgo has zero recurring subscriptions, zero automatic renewals, and zero hidden billing traps. Because the core platform and learning materials are free, students never face unwanted credit card charges or recurring payment obligations.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo enforces deliberate practice: proving invariants, articulating Big-O tradeoffs, managing edge cases, and defending algorithmic approaches to a Senior SWE AI Mock Coach in an integrated Monaco code editor.

15. Bitmask DP: Minimum XOR Sum of Two Arrays (LC 1879) • Invariant Proof & Speed-Run

Theory Context•Dynamic Programming

HardLC 1879

Minimum XOR Sum of Two Arrays (LeetCode 1879)

You will see how one best total per set of used numbers, written as the bits of an integer, replaces n! orders with 2^n states.

Target Frequency:GoogleAmazonMicrosoft

Put nums2 in the order that makes its XOR sum with nums1 as small as possible, and return that smallest sum. nums1 keeps its order, and both arrays have the same length n.

The XOR sum of two arrays lined up position by position adds nums1[i] XOR nums2[i] over every position i. For instance, [1,2] against [3,1] gives (1 XOR 3) + (2 XOR 1) = 2 + 3 = 5.

Worked Examples

Example 1

Input:nums1 = [1,2], nums2 = [2,3]

Output:2

nums1

nums2 reordered

Explanation: Reordering `nums2` to `[3,2]` pairs 1 with 3 (XOR 2) and 2 with 2 (XOR 0): 2. Keeping `[2,3]` gives 3 + 1 = 4.

Example 2

Input:nums1 = [1,0,3], nums2 = [5,3,4]

Output:8

nums1

nums2 reordered

Explanation: Pairing 1 with 5, 0 with 4 and 3 with 3 gives 4 + 4 + 0 = 8, and no order does better.

⚖️Formal Constraints & Bounds

n == nums1.length
n == nums2.length
1 <= n <= 14
0 <= nums1[i], nums2[i] <= 10⁷

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

The rest of the pairing only depends on which nums2 numbers are used, so one best total per set is enough, and the set's size tells which nums1 number comes next: n! orders collapse into 2^n masks.

Real-World Scenario & Production Applications

Assigning n tasks to n workers where each pairing has a cost is the classic assignment problem. When n is small and the cost is irregular, as with scheduling a handful of jobs on machines with setup costs or matching a few sensors to a few readings, one best cost per set of assigned workers finds the optimum without trying every order.

Step-by-Step Execution Trace Table

Example 1, nums1 = [1,2], nums2 = [2,3] (n = 2, four masks). Bit j of the mask means nums2[j] is paired:

Step	`mask`	`i = popcount(mask)`	Free `j`	Relaxation	`dp` after the step
Start				`dp = [0, inf, inf, inf]`	`[0, inf, inf, inf]`
1	`00`	0	0, 1	`dp[01] = 0 + (1 ^ 2) = 3`; `dp[10] = 0 + (1 ^ 3) = 2`	`[0, 3, 2, inf]`
2	`01`	1	1	`dp[11] = 3 + (2 ^ 3) = 4`	`[0, 3, 2, 4]`
3	`10`	1	0	`dp[11] = min(4, 2 + (2 ^ 2)) = 2`	`[0, 3, 2, 2]`
4	`11`	2	none	`i == n`: skip	`[0, 3, 2, 2]`
End				`return dp[11]`	2

Scroll horizontally to see all columns, or expand to full screen

At steps 2 and 3, i is 1 because one bit is set: nums1[0] is already paired, whichever nums2 number it took. Using any other nums1 index there would pair nums1[0] a second time.

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	Only the set of `nums2` numbers already paired matters, so keep one best total per set: `dp[mask]`, where bit `j` of `mask` means `nums2[j]` is used.
2	From each `mask`, pair the next `nums1` number with every free `nums2[j]` and keep the smaller total in `dp[mask \| (1 << j)]`.
3	The shape: one table entry per mask, masks visited from small to large, the next `nums1` index read from the mask, an inner loop over the free `nums2` numbers, and the answer at the full mask.
4	The trap: the next `nums1` index is `i = bin(mask).count("1")`, read from the mask. Pairing any index with the mask loses which `nums1` numbers are used.

Target: Minimum XOR Sum of Two Arrays (LeetCode 1879). Bit `j` of `mask` says whether `nums2[j]` is already paired. Only that set matters for the rest, not the order it was built in, so `n!` orders become `2^n` states.

Boundary Model: Topologically Ordered Subproblem Recurrence (DAG(Directed Acyclic Graph))

Optimal substructure: DP state dp[i] depends strictly on already-computed subproblems. Rolling array reduces space from O(S) to O(1 tier).

Loop Invariant Termination

Iterate base cases -> compute states in topological transition order (dp[i] = min/max/sum of transitions).

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

Trying every way to pair nums1 with nums2 means trying every order of nums2: n! of them, about 87 billion for n = 14. Bitmask DP notices that the future only depends on which nums2 numbers are already used, not on the order they were used in. So it keeps one best total per set, and writes the set as the bits of an integer, mask: 2^n states, about 16,000 for n = 14.

🎭 The Analogy: A Seating Chart

Guests arrive in a fixed order and each takes a free chair. To seat the next guest well, you don't need the story of who sat where first; you only need to know which chairs are taken. Many different histories leave the same chairs taken, and they all continue the same way, so you only keep the cheapest history for each set of taken chairs.

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

dp[0] = 0
for mask in range(1 << n):
    i = bin(mask).count("1")
    for j in range(n):
        if not mask & (1 << j):
            dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + (nums1[i] ^ nums2[j]))

The mask carries everything: its number of set bits is how many nums1 numbers are paired, so nums1[i] with i = bin(mask).count("1") is the next one. Adding a number sets a bit and makes the integer larger, so a plain upward loop over mask reaches every state after all the states that lead into it.

💡 Summary

When n is about 20 or less and only the set of used items matters, index the table by a bitmask, read what you need from the mask itself, and loop masks upward. $O(N \cdot 2^N)$ time and $O(2^N)$ space.

Tracking the nums1 index yourself: i = bin(mask).count("1"). Pairing any nums1 index with the mask forgets which nums1 numbers are used, so one can be paired twice ([2,4,8] with [1,1,1] gives 9 instead of 17).
Dropping the parentheses in the bit test: write mask & (1 << j). In C++, Java or JavaScript, mask & 1 << j == 0 parses as mask & ((1 << j) == 0).
Visiting masks out of order: loop mask from 0 upward and start every entry but dp[0] = 0 at infinity. mask | (1 << j) is always larger, so each state is final before it is read.
Adding a dimension for i: dp[i][mask] works but is n times larger for nothing: i is already the number of bits set in mask.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer spots a small-n assignment and turns it into one state per set of used items.

Pattern Recognition Signals

The 10-second spot

"Put nums2 in the order that makes its XOR sum with nums1 as small as possible", with 1 <= n <= 14: an optimum over orders (n! of them) where only the set of used items matters for the rest. A small n plus "which items are used" is the signal for Bitmask DP.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

dp[mask] is the least XOR sum after pairing the first i = bin(mask).count("1") numbers of nums1 with the nums2 numbers whose bits are set in mask. From each mask, for every free j (not mask & (1 << j)): dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + (nums1[i] ^ nums2[j])). The answer is dp[(1 << n) - 1].

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

i = bin(mask).count("1"), never a separate loop over i: the mask says how many nums1 numbers are paired, and pairing any index lets one be used twice ([2,4,8] with [1,1,1] returns 9 instead of 17).
mask & (1 << j) with the parentheses: in C++, Java or JavaScript mask & 1 << j == 0 compares first and tests the wrong thing.
Loop mask upward from dp[0] = 0, everything else at infinity: mask | (1 << j) is larger than mask, so each state is final before it is read.
Greedy pairing (each nums1 number takes the free nums2 number with the smallest XOR) fails: [0,3,6] with [4,4,2] gives 11 instead of 7.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use Bitmask DP. Trying every order of nums2 is n factorial, but the rest of the problem only depends on which nums2 numbers are already used, so I keep one best total per set, written as the bits of an integer mask. I pair nums1 in order, so the next nums1 index is just the number of bits set in the mask. From each mask I try every free nums2 number, add their XOR, and keep the smaller total in the larger mask. Setting a bit always makes the number bigger, so looping masks upward reads each state after everything that leads into it. The trap is keeping the nums1 index separately: then the mask no longer says which nums1 numbers are used, and one can be paired twice. The answer is the full mask. That's O(N times 2 to the N) time and O(2 to the N) space.

So: dp[mask] per set of used nums2 numbers, i = bin(mask).count("1") for the next nums1 number, masks upward, answer at the full mask.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N * 2^N)

Look at the code: for mask in range(1 << n) runs 2^N times. Inside, bin(mask).count("1") is O(N) and for j in range(n) runs N times with an O(1) bit test, OR and min. Total: 2^N * O(N) = O(N * 2^N).

SPACE COMPLEXITY

O(2^N)

The code keeps one list, dp, with one entry per mask: 2^N entries, plus a few integers. The answer is one integer.

Formal Recurrence Relation

$T(N) = 2^N \cdot (O(N) + N \cdot O(1)) = O(N \cdot 2^N)$

Derivation Progression

States

2^N

for mask in range(1 << n) visits every subset of nums2 once, smallest integer first.

Next index

O(N) per mask

i = bin(mask).count("1") counts the set bits.

Transitions

N per mask

for j in range(n) tests each bit with mask & (1 << j) and relaxes dp[mask | (1 << j)] in O(1).

Total

O(N * 2^N)

2^N masks times O(N) work each; for N = 14 that is about 2.3 * 10^5 steps instead of 14! = 8.7 * 10^10 orders.

Variable Definitions

$N$

Length of nums1 and nums2

Memory Architecture & Bounds

🟣 Call Stack

O(1): iterative, no recursion

🔵 Auxiliary Heap

O(2^N): the dp table

🟢 Output Space

O(1): one integer

Boundary Best / Worst Cases

Best Case

$O(N \cdot 2^N)$ : every mask is visited whatever the numbers are

Average Case

$O(N \cdot 2^N)$

Worst Case

$O(N \cdot 2^N)$

State-Space & Subproblem DAG(Directed Acyclic Graph) Topology

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: **"put nums2in the order that makes its XOR sum withnums1 as small as possible"**, "return that smallest sum", and 1 <= n <= 14. An optimum over orders where only the set of used items matters: Bitmask DP, one state per set.

CONSTRAINTS & BOUNDS

$N \le 14$ : $N! \approx 8.7 \times 10^{10}$ orders is far too many, while $2^{14} = 16{,}384$ masks with 14 tries each is about $2.3 \times 10^5$ steps. Values up to $10^7$ keep every XOR below $2^{24}$ and the total below $2.4 \times 10^8$ , inside 32 bits.

FAANG PRODUCTION TRAPS & EDGE CASES

Tracking the nums1 index outside the mask pairs a number twice. The table has $2^N$ entries, so memory, not time, is usually the first limit: at $N = 20$ it is a million entries, at $N = 30$ a billion; past about 20 items the idea needs meet-in-the-middle or a different model.

Core Algorithmic State Invariants

1. The Set Is the State

`dp[mask]` is the best total with the `nums2` numbers whose bits are set in `mask` already paired. The order they were used in never matters again, so N! orders become 2^N masks.

2. The Mask Names the Next Item (the trap)

`i = bin(mask).count("1")`: one `nums1` number is paired per `nums2` number used, so the mask already says which `nums1` number is next. Choosing `i` freely lets one `nums1` number be paired twice.

3. Masks Upward, N Tries Each

`mask | (1 << j)` is always larger than `mask`, so an upward loop finishes every state before reading it: 2^N masks times N tries, O(N * 2^N) time and O(2^N) space.

Theory Context•Dynamic Programming

HardLC 1879

Minimum XOR Sum of Two Arrays (LeetCode 1879)

You will see how one best total per set of used numbers, written as the bits of an integer, replaces n! orders with 2^n states.

Target Frequency:GoogleAmazonMicrosoft

Put nums2 in the order that makes its XOR sum with nums1 as small as possible, and return that smallest sum. nums1 keeps its order, and both arrays have the same length n.

The XOR sum of two arrays lined up position by position adds nums1[i] XOR nums2[i] over every position i. For instance, [1,2] against [3,1] gives (1 XOR 3) + (2 XOR 1) = 2 + 3 = 5.

Worked Examples

Example 1

Input:nums1 = [1,2], nums2 = [2,3]

Output:2

nums1

nums2 reordered

Explanation: Reordering `nums2` to `[3,2]` pairs 1 with 3 (XOR 2) and 2 with 2 (XOR 0): 2. Keeping `[2,3]` gives 3 + 1 = 4.

Example 2

Input:nums1 = [1,0,3], nums2 = [5,3,4]

Output:8

nums1

nums2 reordered

Explanation: Pairing 1 with 5, 0 with 4 and 3 with 3 gives 4 + 4 + 0 = 8, and no order does better.

⚖️Formal Constraints & Bounds

n == nums1.length
n == nums2.length
1 <= n <= 14
0 <= nums1[i], nums2[i] <= 10⁷

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Real-World Scenario & Production Applications

Step-by-Step Execution Trace Table

Example 1, nums1 = [1,2], nums2 = [2,3] (n = 2, four masks). Bit j of the mask means nums2[j] is paired:

Step	`mask`	`i = popcount(mask)`	Free `j`	Relaxation	`dp` after the step
Start				`dp = [0, inf, inf, inf]`	`[0, inf, inf, inf]`
1	`00`	0	0, 1	`dp[01] = 0 + (1 ^ 2) = 3`; `dp[10] = 0 + (1 ^ 3) = 2`	`[0, 3, 2, inf]`
2	`01`	1	1	`dp[11] = 3 + (2 ^ 3) = 4`	`[0, 3, 2, 4]`
3	`10`	1	0	`dp[11] = min(4, 2 + (2 ^ 2)) = 2`	`[0, 3, 2, 2]`
4	`11`	2	none	`i == n`: skip	`[0, 3, 2, 2]`
End				`return dp[11]`	2

Scroll horizontally to see all columns, or expand to full screen

At steps 2 and 3, i is 1 because one bit is set: nums1[0] is already paired, whichever nums2 number it took. Using any other nums1 index there would pair nums1[0] a second time.

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	Only the set of `nums2` numbers already paired matters, so keep one best total per set: `dp[mask]`, where bit `j` of `mask` means `nums2[j]` is used.
2	From each `mask`, pair the next `nums1` number with every free `nums2[j]` and keep the smaller total in `dp[mask \| (1 << j)]`.
3	The shape: one table entry per mask, masks visited from small to large, the next `nums1` index read from the mask, an inner loop over the free `nums2` numbers, and the answer at the full mask.
4	The trap: the next `nums1` index is `i = bin(mask).count("1")`, read from the mask. Pairing any index with the mask loses which `nums1` numbers are used.

Boundary Model: Topologically Ordered Subproblem Recurrence (DAG(Directed Acyclic Graph))

Optimal substructure: DP state dp[i] depends strictly on already-computed subproblems. Rolling array reduces space from O(S) to O(1 tier).

Loop Invariant Termination

Iterate base cases -> compute states in topological transition order (dp[i] = min/max/sum of transitions).

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🎭 The Analogy: A Seating Chart

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

dp[0] = 0
for mask in range(1 << n):
    i = bin(mask).count("1")
    for j in range(n):
        if not mask & (1 << j):
            dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + (nums1[i] ^ nums2[j]))

💡 Summary

Tracking the nums1 index yourself: i = bin(mask).count("1"). Pairing any nums1 index with the mask forgets which nums1 numbers are used, so one can be paired twice ([2,4,8] with [1,1,1] gives 9 instead of 17).
Dropping the parentheses in the bit test: write mask & (1 << j). In C++, Java or JavaScript, mask & 1 << j == 0 parses as mask & ((1 << j) == 0).
Visiting masks out of order: loop mask from 0 upward and start every entry but dp[0] = 0 at infinity. mask | (1 << j) is always larger, so each state is final before it is read.
Adding a dimension for i: dp[i][mask] works but is n times larger for nothing: i is already the number of bits set in mask.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer spots a small-n assignment and turns it into one state per set of used items.

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

i = bin(mask).count("1"), never a separate loop over i: the mask says how many nums1 numbers are paired, and pairing any index lets one be used twice ([2,4,8] with [1,1,1] returns 9 instead of 17).
mask & (1 << j) with the parentheses: in C++, Java or JavaScript mask & 1 << j == 0 compares first and tests the wrong thing.
Loop mask upward from dp[0] = 0, everything else at infinity: mask | (1 << j) is larger than mask, so each state is final before it is read.
Greedy pairing (each nums1 number takes the free nums2 number with the smallest XOR) fails: [0,3,6] with [4,4,2] gives 11 instead of 7.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use Bitmask DP. Trying every order of nums2 is n factorial, but the rest of the problem only depends on which nums2 numbers are already used, so I keep one best total per set, written as the bits of an integer mask. I pair nums1 in order, so the next nums1 index is just the number of bits set in the mask. From each mask I try every free nums2 number, add their XOR, and keep the smaller total in the larger mask. Setting a bit always makes the number bigger, so looping masks upward reads each state after everything that leads into it. The trap is keeping the nums1 index separately: then the mask no longer says which nums1 numbers are used, and one can be paired twice. The answer is the full mask. That's O(N times 2 to the N) time and O(2 to the N) space.

So: dp[mask] per set of used nums2 numbers, i = bin(mask).count("1") for the next nums1 number, masks upward, answer at the full mask.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N * 2^N)

SPACE COMPLEXITY

O(2^N)

The code keeps one list, dp, with one entry per mask: 2^N entries, plus a few integers. The answer is one integer.

Formal Recurrence Relation

$T(N) = 2^N \cdot (O(N) + N \cdot O(1)) = O(N \cdot 2^N)$

Derivation Progression

States

2^N

for mask in range(1 << n) visits every subset of nums2 once, smallest integer first.

Next index

O(N) per mask

i = bin(mask).count("1") counts the set bits.

Transitions

N per mask

for j in range(n) tests each bit with mask & (1 << j) and relaxes dp[mask | (1 << j)] in O(1).

Total

O(N * 2^N)

2^N masks times O(N) work each; for N = 14 that is about 2.3 * 10^5 steps instead of 14! = 8.7 * 10^10 orders.

Variable Definitions

$N$

Length of nums1 and nums2

Memory Architecture & Bounds

🟣 Call Stack

O(1): iterative, no recursion

🔵 Auxiliary Heap

O(2^N): the dp table

🟢 Output Space

O(1): one integer

Boundary Best / Worst Cases

Best Case

$O(N \cdot 2^N)$ : every mask is visited whatever the numbers are

Average Case

$O(N \cdot 2^N)$

Worst Case

$O(N \cdot 2^N)$

State-Space & Subproblem DAG(Directed Acyclic Graph) Topology

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

1. The Set Is the State

`dp[mask]` is the best total with the `nums2` numbers whose bits are set in `mask` already paired. The order they were used in never matters again, so N! orders become 2^N masks.

2. The Mask Names the Next Item (the trap)

`i = bin(mask).count("1")`: one `nums1` number is paired per `nums2` number used, so the mask already says which `nums1` number is next. Choosing `i` freely lets one `nums1` number be paired twice.

3. Masks Upward, N Tries Each

`mask | (1 << j)` is always larger than `mask`, so an upward loop finishes every state before reading it: 2^N masks times N tries, O(N * 2^N) time and O(2^N) space.

Rosetta Dual-Monaco Comparison

Python 3

CANONICAL INVARIANT TEMPLATE

CONCRETE: MINIMUM XOR SUM OF TWO ARRAYS (LEETCODE 1879)

T = O(N * 2^N)S = O(2^N)

Pattern Implementation Mapping TableCanonical Invariant ⟷ Concrete Code ⟷ Engineering Rationale

Canonical Invariant	Concrete Code	Engineering Rationale
One best answer per set of used items	`dp = [float("inf")] * (1 << n)`	Bit `j` of `mask` says whether `nums2[j]` is already paired. Only that set matters for the rest, not the order it was built in, so `n!` orders become `2^n` states.
The empty set	`dp[0] = 0`	Nothing paired, nothing added yet.
Masks from small to large	`for mask in range(1 << n):`	Every transition sets a bit, so it goes to a larger number: when a mask is read, every way into it has been tried.
The next item comes from the mask (the trap)	`i = bin(mask).count("1")`	`nums1` is paired in order, one number per `nums2` number used, so the mask already says which `nums1` number is next. Tracking `i` separately loses that link.
Try every free item	`if not mask & (1 << j): nxt = mask \| (1 << j)`	`mask & (1 << j)` tests bit `j`, and `mask \| (1 << j)` marks it used.
Relax the larger state	`dp[nxt] = min(dp[nxt], dp[mask] + (nums1[i] ^ nums2[j]))`	Pairing `nums1[i]` with `nums2[j]` costs their XOR on top of the best way to reach `mask`.
Answer at the full set	`return dp[(1 << n) - 1]`	All `n` bits set: every number of `nums2` is paired.

Step

mask

i = popcount(mask)

Free j

Relaxation

dp after the step

Start

dp = [0, inf, inf, inf]

[0, inf, inf, inf]

00

0, 1

dp[01] = 0 + (1 ^ 2) = 3; dp[10] = 0 + (1 ^ 3) = 2

[0, 3, 2, inf]

01

dp[11] = 3 + (2 ^ 3) = 4

[0, 3, 2, 4]

10

dp[11] = min(4, 2 + (2 ^ 2)) = 2

[0, 3, 2, 2]

11

none

i == n: skip

[0, 3, 2, 2]

End

return dp[11]

dp[0] = 0 for mask in range(1 << n): i = bin(mask).count("1") for j in range(n): if not mask & (1 << j): dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + (nums1[i] ^ nums2[j]))

Step

mask

i = popcount(mask)

Free j

Relaxation

dp after the step

Start

dp = [0, inf, inf, inf]

[0, inf, inf, inf]

00

0, 1

dp[01] = 0 + (1 ^ 2) = 3; dp[10] = 0 + (1 ^ 3) = 2

[0, 3, 2, inf]

01

dp[11] = 3 + (2 ^ 3) = 4

[0, 3, 2, 4]

10

dp[11] = min(4, 2 + (2 ^ 2)) = 2

[0, 3, 2, 2]

11

none

i == n: skip

[0, 3, 2, 2]

End

return dp[11]

dp[0] = 0 for mask in range(1 << n): i = bin(mask).count("1") for j in range(n): if not mask & (1 << j): dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + (nums1[i] ^ nums2[j]))

Canonical Invariant

Concrete Code

Engineering Rationale

One best answer per set of used items

dp = [float("inf")] * (1 << n)

Bit `j` of `mask` says whether `nums2[j]` is already paired. Only that set matters for the rest, not the order it was built in, so `n!` orders become `2^n` states.

The empty set

dp[0] = 0

Nothing paired, nothing added yet.

Masks from small to large

for mask in range(1 << n):

Every transition sets a bit, so it goes to a larger number: when a mask is read, every way into it has been tried.

The next item comes from the mask (the trap)

i = bin(mask).count("1")

`nums1` is paired in order, one number per `nums2` number used, so the mask already says which `nums1` number is next. Tracking `i` separately loses that link.

Try every free item

if not mask & (1 << j):
    nxt = mask | (1 << j)

`mask & (1 << j)` tests bit `j`, and `mask | (1 << j)` marks it used.

Relax the larger state

dp[nxt] = min(dp[nxt], dp[mask] + (nums1[i] ^ nums2[j]))

Pairing `nums1[i]` with `nums2[j]` costs their XOR on top of the best way to reach `mask`.

Answer at the full set

return dp[(1 << n) - 1]

All `n` bits set: every number of `nums2` is paired.