Minimum XOR Sum of Two Arrays (LeetCode 1879)
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
nums1 = [1,2], nums2 = [2,3]2nums2 to [3,2] pairs 1 with 3 (XOR 2) and 2 with 2 (XOR 0): 2. Keeping [2,3] gives 3 + 1 = 4.nums1 = [1,0,3], nums2 = [5,3,4]8⚖️Formal Constraints & Bounds
n == nums1.lengthn == nums2.length1 <= n <= 140 <= nums1[i], nums2[i] <= 107
Core Insight
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 |
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.
| 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. |
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.
🔑 Why It Works
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.
Tracking the
nums1index yourself:i = bin(mask).count("1"). Pairing anynums1index with the mask does not record whichnums1numbers 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++ or JavaScript,mask & 1 << j == 0parses asmask & ((1 << j) == 0), which is always 0; in Java it does not compile.Visiting masks out of order: loop
maskfrom 0 upward and start every entry butdp[0] = 0at 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 isntimes larger for nothing:iis already the number of bits set inmask.
4-Phase Thought Process Model
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
Greedy pairing (each
nums1number takes the freenums2number 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.
Complexity & Mathematical Proof
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).
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.
Derivation Progression
2^N
for mask in range(1 << n) visits every subset of nums2 once, smallest integer first.
O(N) per mask
i = bin(mask).count("1") counts the set bits.
N per mask
for j in range(n) tests each bit with mask & (1 << j) and relaxes dp[mask | (1 << j)] in O(1).
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
Length of nums1 and nums2
Memory Architecture & Bounds
O(1): iterative, no recursion
O(2^N): the dp table
O(1): one integer
Boundary Best / Worst Cases
: every mask is visited whatever the numbers are
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "put nums2 in the order that makes its XOR sum with nums1 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.
: orders is far too many, while masks with 14 tries each is about steps. Values up to keep every XOR below and the total below , inside 32 bits.
The table has entries, so memory, not time, is usually the first limit: at it is a million entries, at a billion; past about 20 items the idea needs meet-in-the-middle or a different model.
Minimum XOR Sum of Two Arrays (LeetCode 1879)
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
nums1 = [1,2], nums2 = [2,3]2nums2 to [3,2] pairs 1 with 3 (XOR 2) and 2 with 2 (XOR 0): 2. Keeping [2,3] gives 3 + 1 = 4.nums1 = [1,0,3], nums2 = [5,3,4]8⚖️Formal Constraints & Bounds
n == nums1.lengthn == nums2.length1 <= n <= 140 <= nums1[i], nums2[i] <= 107
Core Insight
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 |
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.
| 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. |
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.
🔑 Why It Works
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.
Tracking the
nums1index yourself:i = bin(mask).count("1"). Pairing anynums1index with the mask does not record whichnums1numbers 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++ or JavaScript,mask & 1 << j == 0parses asmask & ((1 << j) == 0), which is always 0; in Java it does not compile.Visiting masks out of order: loop
maskfrom 0 upward and start every entry butdp[0] = 0at 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 isntimes larger for nothing:iis already the number of bits set inmask.
4-Phase Thought Process Model
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
Greedy pairing (each
nums1number takes the freenums2number 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.
Complexity & Mathematical Proof
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).
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.
Derivation Progression
2^N
for mask in range(1 << n) visits every subset of nums2 once, smallest integer first.
O(N) per mask
i = bin(mask).count("1") counts the set bits.
N per mask
for j in range(n) tests each bit with mask & (1 << j) and relaxes dp[mask | (1 << j)] in O(1).
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
Length of nums1 and nums2
Memory Architecture & Bounds
O(1): iterative, no recursion
O(2^N): the dp table
O(1): one integer
Boundary Best / Worst Cases
: every mask is visited whatever the numbers are
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "put nums2 in the order that makes its XOR sum with nums1 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.
: orders is far too many, while masks with 14 tries each is about steps. Values up to keep every XOR below and the total below , inside 32 bits.
The table has entries, so memory, not time, is usually the first limit: at it is a million entries, at a billion; past about 20 items the idea needs meet-in-the-middle or a different model.