Minimum XOR Sum of Two Arrays — Bitmask DP with XOR Pairing

Problem Statement#

You are given two integer arrays nums1 and nums2 of equal length n. The XOR sum is defined as:

(nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n-1] XOR nums2[n-1])

Rearrange the elements of nums2 so that the XOR sum is minimized. Return the minimum XOR sum.

Constraints:

• 1 <= n <= 14
• 0 <= nums1[i], nums2[i] <= 10^7

Examples:

Input:  nums1 = [1,2], nums2 = [2,3]
Output: 2
Explanation: Rearrange nums2 -> [3,2]. Sum = (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.
 
Input:  nums1 = [1,0,3], nums2 = [5,3,4]
Output: 8
Explanation: Rearrange nums2 -> [5,4,3]. Sum = (1^5)+(0^4)+(3^3) = 4+4+0 = 8.
 
Input:  nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 14

Why This Problem Matters#

This is a textbook assignment problem wearing a bit manipulation costume. The Hungarian algorithm solves it in polynomial time, but in interviews you'll be asked the bitmask DP variant — it's cleaner, fits the small n <= 14 constraint, and showcases two skills hiring managers love: XOR intuition and state compression DP. Google, Amazon, and Meta all rotate this style of problem because it rewards candidates who recognize that "match each item to exactly one other" plus "n is tiny" equals bitmask DP.

The Core Insight (the bit-trick)#

XOR has no closed form for "minimum pairing" — there's no greedy that always works. Instead, we compress the assignment state into a single integer. With n <= 14, every subset of nums2 fits in a 14-bit mask.

Define:

dp[mask] = minimum XOR sum achievable when the bits set in mask represent the indices of nums2 already paired.

The number of set bits in mask (popcount) tells us how many elements of nums1 we've already processed — meaning the next element to pair is nums1[popcount(mask)]. This eliminates the second dimension entirely. We try pairing it with each unset bit j in mask:

dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + (nums1[i] XOR nums2[j]))

The final answer is dp[(1 << n) - 1] — the state where every nums2 index is consumed.

Visual Dry Run (binary representation trace)#

Take nums1 = [1, 2], nums2 = [2, 3]. n = 2, so masks are 2-bit.

mask=00 (0): popcount=0, i=0 -> pair nums1[0]=1 with nums2[?]
  j=0: dp[01] = dp[00] + (1 XOR 2) = 0 + 3 = 3
  j=1: dp[10] = dp[00] + (1 XOR 3) = 0 + 2 = 2
 
mask=01 (1): popcount=1, i=1 -> pair nums1[1]=2
  j=1: dp[11] = dp[01] + (2 XOR 3) = 3 + 1 = 4
 
mask=10 (2): popcount=1, i=1 -> pair nums1[1]=2
  j=0: dp[11] = min(4, dp[10] + (2 XOR 2)) = min(4, 2 + 0) = 2
 
Answer: dp[11] = 2

Notice how mask=10 (using nums2[1] first) leads to the optimal pairing — greedy by smallest XOR per step would have picked (1 XOR 2)=3 first and missed it.

Solution (Optimal)#

Python#

class Solution:
    def minimumXORSum(self, nums1: list[int], nums2: list[int]) -> int:
        n = len(nums1)
        FULL = (1 << n) - 1
        dp = [float('inf')] * (1 << n)
        dp[0] = 0
 
        for mask in range(1 << n):
            if dp[mask] == float('inf'):
                continue
            i = bin(mask).count('1')   # next index in nums1
            if i == n:
                continue
            for j in range(n):
                if not (mask & (1 << j)):
                    new_mask = mask | (1 << j)
                    cost = dp[mask] + (nums1[i] ^ nums2[j])
                    if cost < dp[new_mask]:
                        dp[new_mask] = cost
 
        return dp[FULL]

JavaScript#

var minimumXORSum = function (nums1, nums2) {
  const n = nums1.length;
  const FULL = (1 << n) - 1;
  const dp = new Array(1 << n).fill(Infinity);
  dp[0] = 0;
 
  const popcount = (x) => {
    let c = 0;
    while (x) { x &= x - 1; c++; }
    return c;
  };
 
  for (let mask = 0; mask <= FULL; mask++) {
    if (dp[mask] === Infinity) continue;
    const i = popcount(mask);
    if (i === n) continue;
    for (let j = 0; j < n; j++) {
      if (!(mask & (1 << j))) {
        const nm = mask | (1 << j);
        const cost = dp[mask] + (nums1[i] ^ nums2[j]);
        if (cost < dp[nm]) dp[nm] = cost;
      }
    }
  }
  return dp[FULL];
};

Complexity: Time O(2^n * n) (2^14 * 14 ~= 230K ops). Space O(2^n).

Common Mistakes#

• Trying greedy XOR matching. Picking the locally smallest XOR pair fails — XOR is non-monotonic.
• Mismatched index inference. Forgetting that popcount(mask) already encodes the nums1 index leads people to add a redundant DP dimension and blow up memory.
• Off-by-one on FULL. Use (1 << n) - 1, not 1 << n.
• Iterating masks in the wrong order. Iterate mask ascending — every transition only writes to a mask with strictly more set bits.
• Skipping the dp[mask] == inf guard. Without it you waste cycles on unreachable states (rare here but matters in larger DPs).

Interview Tips#

• Open with: "n is at most 14, that screams bitmask DP — 2^14 is only 16,384 states." That single sentence signals you've seen the pattern.
• Walk through why greedy fails before writing code. Interviewers reward candidates who justify the heavy hammer.
• When asked for optimization, mention the Hungarian algorithm (O(n^3)) — same answer, better asymptotics. You won't code it, but knowing it exists shows depth.
• Discuss iterative vs memoized recursion. Iterative bottom-up is cache-friendly; recursive with lru_cache is shorter to write.

Follow-up Questions#

1. Maximize XOR sum instead. Replace min with max and initialize to -inf.
2. What if arrays have different lengths? Pad the shorter one with zeros — XOR with 0 is identity.
3. n up to 20? 2^20 * 20 = ~20M ops, still fine. At n=25, switch to Hungarian.
4. Can you reconstruct the assignment? Store a parent[mask] recording which j produced each transition; backtrack from FULL.
5. Online version where nums2 streams in? You can no longer enumerate all permutations — falls back to min-cost bipartite matching.

Key Takeaways#

• n <= 14 plus "assign every i to a unique j" is the canonical signature of bitmask DP for assignment.
• Use popcount(mask) to recover the implicit nums1 index — saves a DP dimension.
• XOR pairing is not greedy-friendly; always model it as state-space search.
• Time O(2^n * n), space O(2^n) — memorize this complexity for FAANG interviews.
• Iterate masks in ascending order so every transition flows from fewer-bits to more-bits states.
• Knowing the Hungarian algorithm exists is the polish that separates a strong hire from a meets-bar candidate.