Minimum XOR Sum of Two Arrays

Hard
1340.

Minimum XOR Sum of Two Arrays

Minimum XOR Sum of Two Arrays is a hard coding problem on arrays, dynamic programming and bit manipulation, asked in Amazon and Google interviews.

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.length
  • n == nums2.length
  • 1 <= n <= 14
  • 0 <= nums1[i], nums2[i] <= 10^7
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var minimumXORSum = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • n == nums2.length
  • 1 <= n <= 14
  • 0 <= nums1[i], nums2[i] <= 10^7

Hints for Minimum XOR Sum of Two Arrays

  1. Hint 1

    This is an assignment problem: match each nums1[i] with a distinct nums2[j] at cost nums1[i] XOR nums2[j].

  2. Hint 2

    Trying all n! orders is too many for n = 14, but the set of already-used nums2 elements fits in a 14-bit mask.

  3. Hint 3

    Let dp[mask] be the cheapest way to match the first popcount(mask) elements of nums1 with the elements of nums2 in mask. Extend it by matching the next nums1 element with each unused j.

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

  1. Set dp[0] = 0 and every other dp[mask] to infinity.
  2. Visit masks in increasing order. With i = popcount(mask) (the next nums1 index), for each j not in mask update dp[mask | 1<<j] with dp[mask] + (nums1[i] XOR nums2[j]).
  3. 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 nums1 index 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