Minimum XOR Sum of Two Arrays

Minimum XOR Sum of Two Arrays

What is this problem about?

The Minimum XOR Sum of Two Arrays problem gives you two integer arrays of equal length. You can rearrange the second array in any order. Find the permutation of the second array that minimizes the sum of XOR values (arr1[0]^arr2[p[0]] + arr1[1]^arr2[p[1]] + ...). This Minimum XOR Sum of Two Arrays coding problem is a bitmask DP assignment problem — a classic hard-level challenge.

Why is this asked in interviews?

Media.net asks this because it's a canonical bitmask DP problem where you assign n items (from arr2) to n slots (from arr1) optimally. The XOR cost function makes greedy matching unreliable, forcing the use of bitmask DP to explore all assignments. The array, bitmask, bit manipulation, and dynamic programming interview pattern is fully tested here.

Algorithmic pattern used

Bitmask DP assignment. dp[mask] = minimum XOR sum when mask represents which elements of arr2 have already been assigned. Let i = popcount(mask) (index into arr1). For each element j in arr2 not yet assigned (bit j not set in mask), try assigning arr2[j] to arr1[i]: dp[mask | (1<<j)] = min(dp[mask | (1<<j)], dp[mask] + arr1[i] ^ arr2[j]). Final answer: dp[(1<<n)-1].

Example explanation

arr1 = [1, 2], arr2 = [2, 3].

• Assign arr2[0]=2 to arr1[0]=1: XOR = 1^2 = 3. Then arr2[1]=3 to arr1[1]=2: XOR = 2^3 = 1. Total = 4.
• Assign arr2[1]=3 to arr1[0]=1: XOR = 1^3 = 2. Then arr2[0]=2 to arr1[1]=2: XOR = 2^2 = 0. Total = 2. Minimum = 2.

Common mistakes candidates make

• Using greedy matching (doesn't work for XOR — the optimal assignment is non-obvious).
• popcount(mask) computation errors (use built-in bin(mask).count('1') or bit tricks).
• Not memoizing: the bitmask DP has 2^n states, but without memoization it's exponential.
• Wrong transition: assigning to arr1[mask_popcount] instead of arr1[i].

Interview preparation tip

Minimum XOR Sum of Two Arrays is the standard example of bitmask DP for optimal assignment. The template: dp[mask] = best cost assigning items corresponding to set bits in mask, with the next item to assign (into arr1) being arr1[popcount(mask)]. Practice this template on similar assignment problems: minimum cost bipartite matching, minimum sum pairing, optimal job assignment. n ≤ 14 is the typical indicator that bitmask DP is the intended solution (2^14 = 16384 states).