Problem

You are given two integer arrays nums1 and nums2 of length n.

The XOR sum of the two integer arrays is (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]) (0-indexed).

  • For example, the XOR sum of [1,2,3] and [3,2,1] is equal to (1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4.

Rearrange the elements of nums2 such that the resulting XOR sum is minimized.

Return theXOR sum after the rearrangement.

Examples

Example 1

1
2
3
4

Input: nums1 = [1,2], nums2 = [2,3]
Output: 2
Explanation: Rearrange nums2 so that it becomes [3,2].
The XOR sum is (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.

Example 2

1
2
3
4

Input: nums1 = [1,0,3], nums2 = [5,3,4]
Output: 8
Explanation: Rearrange nums2 so that it becomes [5,4,3]. 
The XOR sum is (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8.

Constraints

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

Solution

Method 1 – Bitmask Dynamic Programming

Intuition

This problem is a variant of the assignment problem, where we want to pair each element in nums1 with a unique element in nums2 to minimize the total XOR sum. Since n is small (≤ 14), we can use bitmask DP to efficiently try all possible assignments.

Approach

  1. Use a DP array where dp[mask] is the minimum XOR sum for a given assignment mask.
  2. For each state, try assigning the next nums1 element to every unused nums2 element.
  3. Use recursion with memoization to avoid recomputation.
  4. The answer is dp[0] (no elements assigned yet).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> dp(1 << n, INT_MAX);
        dp[0] = 0;
        for (int mask = 0; mask < (1 << n); ++mask) {
            int i = __builtin_popcount(mask);
            for (int j = 0; j < n; ++j) {
                if (!(mask & (1 << j))) {
                    int next = mask | (1 << j);
                    dp[next] = min(dp[next], dp[mask] + (nums1[i] ^ nums2[j]));
                }
            }
        }
        return dp[(1 << n) - 1];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func MinimumXORSum(nums1, nums2 []int) int {
    n := len(nums1)
    dp := make([]int, 1<<n)
    for i := range dp {
        dp[i] = 1<<31 - 1
    }
    dp[0] = 0
    for mask := 0; mask < 1<<n; mask++ {
        i := bits.OnesCount(uint(mask))
        for j := 0; j < n; j++ {
            if mask&(1<<j) == 0 {
                next := mask | (1 << j)
                if dp[next] > dp[mask]+(nums1[i]^nums2[j]) {
                    dp[next] = dp[mask] + (nums1[i] ^ nums2[j])
                }
            }
        }
    }
    return dp[(1<<n)-1]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int minimumXORSum(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] dp = new int[1 << n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            int i = Integer.bitCount(mask);
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) == 0) {
                    int next = mask | (1 << j);
                    dp[next] = Math.min(dp[next], dp[mask] + (nums1[i] ^ nums2[j]));
                }
            }
        }
        return dp[(1 << n) - 1];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun minimumXORSum(nums1: IntArray, nums2: IntArray): Int {
        val n = nums1.size
        val dp = IntArray(1 shl n) { Int.MAX_VALUE }
        dp[0] = 0
        for (mask in 0 until (1 shl n)) {
            val i = mask.countOneBits()
            for (j in 0 until n) {
                if (mask and (1 shl j) == 0) {
                    val next = mask or (1 shl j)
                    dp[next] = minOf(dp[next], dp[mask] + (nums1[i] xor nums2[j]))
                }
            }
        }
        return dp[(1 shl n) - 1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from typing import List
class Solution:
    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        dp = [float('inf')] * (1 << n)
        dp[0] = 0
        for mask in range(1 << n):
            i = bin(mask).count('1')
            for j in range(n):
                if not (mask & (1 << j)):
                    next_mask = mask | (1 << j)
                    dp[next_mask] = min(dp[next_mask], dp[mask] + (nums1[i] ^ nums2[j]))
        return dp[(1 << n) - 1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn minimum_xor_sum(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let n = nums1.len();
        let mut dp = vec![i32::MAX; 1 << n];
        dp[0] = 0;
        for mask in 0..(1 << n) {
            let i = mask.count_ones() as usize;
            for j in 0..n {
                if (mask & (1 << j)) == 0 {
                    let next = mask | (1 << j);
                    dp[next] = dp[next].min(dp[mask] + (nums1[i] ^ nums2[j]));
                }
            }
        }
        dp[(1 << n) - 1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    minimumXORSum(nums1: number[], nums2: number[]): number {
        const n = nums1.length;
        const dp = Array(1 << n).fill(Number.POSITIVE_INFINITY);
        dp[0] = 0;
        for (let mask = 0; mask < (1 << n); mask++) {
            const i = mask.toString(2).split('1').length - 1;
            for (let j = 0; j < n; j++) {
                if ((mask & (1 << j)) === 0) {
                    const next = mask | (1 << j);
                    dp[next] = Math.min(dp[next], dp[mask] + (nums1[i] ^ nums2[j]));
                }
            }
        }
        return dp[(1 << n) - 1];
    }
}

Complexity

  • ⏰ Time complexity: O(n^2 * 2^n) — There are 2^n states and for each state up to n transitions.
  • 🧺 Space complexity: O(2^n) — The DP array stores results for each mask.