LeetCode 1879 - Minimum XOR Sum of Two Arrays

The problem asks us to take two integer arrays of equal length, nums1 and nums2, and rearrange the elements of nums2 to minimize the XOR sum. The XOR sum is computed as (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]).

leetcodehardarraydynamic-programmingbit-manipulationbitmask

LeetCode Problem 1879

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Bit Manipulation, Bitmask

Solution

Problem Understanding

The problem asks us to take two integer arrays of equal length, nums1 and nums2, and rearrange the elements of nums2 to minimize the XOR sum. The XOR sum is computed as (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]). The task is to find the minimum possible sum achievable by permuting nums2.

The input arrays are guaranteed to have lengths up to 14, and their elements range between 0 and 10^7. This small n implies that solutions that may have exponential time in n are feasible if implemented efficiently. Key constraints and edge cases include arrays of length 1, arrays with identical elements, and arrays where XOR values have large differences, since XOR is highly non-linear and not monotonic.

Naive or greedy approaches, such as always pairing the smallest numbers together, may fail because XOR does not preserve order or magnitude intuitions like addition or multiplication.

Approaches

Brute-Force Approach

A brute-force approach would consider all permutations of nums2 and compute the XOR sum for each permutation. This guarantees the correct answer, but has factorial complexity: O(n!). With n up to 14, 14! ≈ 87 billion operations, which is clearly infeasible.

Optimal Approach

The key insight is that we can represent the problem using dynamic programming with bitmasking. Each state in the DP represents a set of elements in nums2 that have already been used. We can encode this as a bitmask of length n. For each state, we track the minimal XOR sum achievable. This allows us to explore all possible pairings efficiently using memoization.

The DP recurrence is:

dp(mask) = min(dp(mask | (1 << j)) + nums1[i] XOR nums2[j] for all j where bit j in mask is 0)

Here, i is the number of 1s in the current mask, representing which index in nums1 we are currently pairing. This reduces the time complexity to O(n * 2^n), which is feasible for n <= 14.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Check all permutations of nums2
DP with Bitmask O(n * 2^n) O(2^n) Each state represents used indices of nums2

Algorithm Walkthrough

  1. Initialize a memoization table dp as a dictionary to store the minimum XOR sum for each bitmask.
  2. Define a recursive function dfs(mask) which returns the minimum XOR sum for the current mask.
  3. Compute the number of elements already paired (i) as the number of 1s in mask.
  4. If i == n, return 0 because all elements are paired.
  5. If mask exists in dp, return the stored value.
  6. Iterate over all indices j of nums2. For each index where the j-th bit of mask is 0, recursively compute the XOR sum by pairing nums1[i] with nums2[j] and adding it to dfs(mask | (1 << j)).
  7. Store the minimum result in dp[mask] and return it.
  8. Call dfs(0) to start with no elements paired.

Why it works: This approach guarantees that all possible pairings are considered, but uses memoization to avoid recalculating overlapping subproblems. The bitmask encodes the state efficiently, allowing a full exploration of permutations in O(n * 2^n) time.

Python Solution

from typing import List

class Solution:
    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        dp = {}
        
        def dfs(mask: int) -> int:
            i = bin(mask).count('1')
            if i == n:
                return 0
            if mask in dp:
                return dp[mask]
            
            min_sum = float('inf')
            for j in range(n):
                if not (mask & (1 << j)):
                    current_sum = (nums1[i] ^ nums2[j]) + dfs(mask | (1 << j))
                    min_sum = min(min_sum, current_sum)
            
            dp[mask] = min_sum
            return min_sum
        
        return dfs(0)

The implementation defines a recursive DFS function with memoization. The mask represents which elements of nums2 have been used. At each recursion, we pair the next element of nums1 with all available elements of nums2, updating the mask accordingly. The memoization table avoids redundant computations and ensures efficient exploration.

Go Solution

func minimumXORSum(nums1 []int, nums2 []int) int {
    n := len(nums1)
    dp := make(map[int]int)
    
    var dfs func(int) int
    dfs = func(mask int) int {
        i := 0
        for m := mask; m > 0; m >>= 1 {
            i += m & 1
        }
        if i == n {
            return 0
        }
        if val, exists := dp[mask]; exists {
            return val
        }
        
        minSum := 1<<60
        for j := 0; j < n; j++ {
            if mask&(1<<j) == 0 {
                currentSum := (nums1[i] ^ nums2[j]) + dfs(mask|(1<<j))
                if currentSum < minSum {
                    minSum = currentSum
                }
            }
        }
        dp[mask] = minSum
        return minSum
    }
    
    return dfs(0)
}

The Go solution mirrors the Python approach, using a map[int]int for memoization. Counting set bits requires an explicit loop. Otherwise, the DFS and bitmask logic is identical.

Worked Examples

Example 1: nums1 = [1,2], nums2 = [2,3]

Step Mask i Choices Min Sum
Start 00 0 Pair 1 with 2 or 3 2
Pair 1 with 3 10 1 Pair 2 with 2 2
Pair 1 with 2 01 1 Pair 2 with 3 4
Result 2

Example 2: nums1 = [1,0,3], nums2 = [5,3,4]

Step Mask i Choices Min Sum
Start 000 0 Pair 1 with 5,3,4
Pair 1 with 5 001 1 Pair 0 with 3,4 8
Pair 1 with 4 100 1 Pair 0 with 5,3 10
Pair 1 with 3 010 1 Pair 0 with 5,4 11
Result 8

Complexity Analysis

Measure Complexity Explanation
Time O(n * 2^n) Each bitmask (2^n) is computed once, iterating over n options to pair
Space O(2^n) Memoization table stores a result for each bitmask

The exponential factor in 2^n is feasible since n <= 14.

Test Cases

# Provided examples
assert Solution().minimumXORSum([1,2], [2,3]) == 2  # minimal XOR sum
assert Solution().minimumXORSum([1,0,3], [5,3,4]) == 8  # minimal XOR sum

# Edge cases
assert Solution().minimumXORSum([0], [0]) == 0  # single element, zero XOR
assert Solution().minimumXORSum([1], [1]) == 0  # single element, XOR same
assert Solution().minimumXORSum([1,1,1], [0,0,0]) == 3  # all ones vs zeros
assert Solution().minimumXORSum([1,2,3,4], [4,3,2,1]) == 0  # perfect rearrangement
assert Solution().minimumXORSum([5,5,5], [5,5,5]) == 0  # identical arrays
Test Why
[1,2], [2,3] Minimal XOR achievable by rearranging
[1,0,3], [5,3,4] Multiple pairings, checks DP correctness
[0], [0] Single element, trivial case
[1], [1] Single element, XOR zero
[1,1,1], [0,0,0] All elements same, XORs sum to n
[1,2,