Minimum XOR Sum of Two Arrays — Problem & Solution
Minimum XOR Sum of Two Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimum XOR Sum of Two Arrays is a hard coding problem on arrays, dynamic programming and bit manipulation, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Bit Manipulation, Bitmask
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two integer arrays nums1 and nums2 of the same length n. Their XOR sum is (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n-1] XOR nums2[n-1]).
You may rearrange the elements of nums2 in any order. Return the smallest XOR sum you can achieve.
Example 1
Input: nums1 = [4,7], nums2 = [6,5]
Output: 2
Explanation: Rearranged as `[5,6]`: `(4 XOR 5) + (7 XOR 6) = 1 + 1`.
Example 2
Input: nums1 = [0,0,0], nums2 = [1,2,3]
Output: 6
Example 3
Input: nums1 = [9], nums2 = [9]
Output: 0
Constraints
n == nums1.lengthn == nums2.length1 <= n <= 140 <= nums1[i], nums2[i] <= 10^7
Hints for Minimum XOR Sum of Two Arrays
Hint 1
This is an assignment problem: match each
nums1[i]with a distinctnums2[j]at costnums1[i] XOR nums2[j].Hint 2
Trying all n! orders is too many for n = 14, but the set of already-used
nums2elements fits in a 14-bit mask.Hint 3
Let
dp[mask]be the cheapest way to match the firstpopcount(mask)elements ofnums1with the elements ofnums2inmask. Extend it by matching the nextnums1element with each unusedj.
How to solve Minimum XOR Sum of Two Arrays
Match nums1 in order. After matching the first i elements, only which nums2 elements are used matters — a bitmask — so a DP over the 2^n masks replaces the n! permutations.
Approach
- Set
dp[0] = 0and every otherdp[mask]to infinity. - Visit masks in increasing order. With
i = popcount(mask)(the nextnums1index), for eachjnot inmaskupdatedp[mask | 1<<j]withdp[mask] + (nums1[i] XOR nums2[j]). - Return
dp[2^n - 1].
Why it works
Any rearrangement assigns nums1[0], nums1[1], … in turn to distinct nums2 elements, so it is a path from the empty mask to the full mask that adds exactly its XOR terms. The cost of finishing depends only on which elements are still free, so keeping the cheapest cost per mask loses nothing. Masks only grow, so increasing order processes each mask after all its predecessors.
Complexity
- Time —
O(n · 2^n) - Space —
O(2^n)
Pitfalls
- Greedy pairing (sorting both arrays, or always taking the closest XOR) is not optimal.
- The
nums1index is the popcount of the mask, not a separate DP dimension. - The sum stays below 14 · 2^24, so a 32-bit integer suffices, but the infinity value must not overflow when an edge cost is added.
Reference solution
Python
from typing import List
def minimumXORSum(nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
full = 1 << n
inf = float("inf")
dp = [inf] * full
dp[0] = 0
for mask in range(full):
cur = dp[mask]
i = bin(mask).count("1")
if i >= n:
continue
a = nums1[i]
for j in range(n):
if mask & (1 << j):
continue
nm = mask | (1 << j)
v = cur + (a ^ nums2[j])
if v < dp[nm]:
dp[nm] = v
return dp[full - 1]Java
public static int minimumXORSum(int[] nums1, int[] nums2) {
int n = nums1.length, full = 1 << n;
int[] dp = new int[full];
Arrays.fill(dp, 1 << 30);
dp[0] = 0;
for (int mask = 0; mask < full; mask++) {
int i = Integer.bitCount(mask);
if (i >= n) continue;
for (int j = 0; j < n; j++) {
if ((mask & (1 << j)) != 0) continue;
int nm = mask | (1 << j);
dp[nm] = Math.min(dp[nm], dp[mask] + (nums1[i] ^ nums2[j]));
}
}
return dp[full - 1];
}C++
int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), full = 1 << n;
vector<int> dp(full, 1 << 30);
dp[0] = 0;
for (int mask = 0; mask < full; mask++) {
int i = __builtin_popcount(mask);
if (i >= n) continue;
for (int j = 0; j < n; j++) {
if (mask & (1 << j)) continue;
int nm = mask | (1 << j);
dp[nm] = min(dp[nm], dp[mask] + (nums1[i] ^ nums2[j]));
}
}
return dp[full - 1];
}JavaScript
var minimumXORSum = function(nums1, nums2) {
var n = nums1.length, full = 1 << n;
var dp = new Array(full).fill(Infinity), pc = new Array(full).fill(0);
dp[0] = 0;
for (var mask = 0; mask < full; mask++) {
if (mask) pc[mask] = pc[mask >> 1] + (mask & 1);
var i = pc[mask];
if (i >= n) continue;
for (var j = 0; j < n; j++) {
if (mask & (1 << j)) continue;
var nm = mask | (1 << j), v = dp[mask] + (nums1[i] ^ nums2[j]);
if (v < dp[nm]) dp[nm] = v;
}
}
return dp[full - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming