Minimum XOR Sum of Two Arrays

• The core idea is to generate every possible arrangement (permutation) of the nums2 array.
• For each permutation of nums2, we calculate the XOR sum by pairing nums1[i] with the i-th element of the permuted nums2.
• We maintain a global variable to keep track of the minimum XOR sum found so far across all permutations.
• This can be implemented using a recursive backtracking function that generates all permutations.
• The steps for the recursive function permute(index, current_nums2) are:
  • Base Case: If index reaches the length of the array n, it means we have a full permutation. Calculate the XOR sum for this permutation and update the global minimum.
  • Recursive Step: Iterate a loop from i = index to n-1. In each iteration:
    • Swap current_nums2[index] with current_nums2[i] to place a new element at the current position.
    • Make a recursive call for the next position: permute(index + 1, current_nums2).
    • Backtrack by swapping current_nums2[index] and current_nums2[i] back to their original positions. This is crucial to explore all possible permutations correctly.

This approach tackles the problem by exploring the entire search space of permutations. The problem asks to rearrange nums2 to minimize the XOR sum. A rearrangement of nums2 is simply a permutation. Therefore, we can systematically generate all permutations of nums2. For each generated permutation, we compute the XOR sum against the fixed nums1 array: (nums1[0] XOR p_nums2[0]) + (nums1[1] XOR p_nums2[1]) + .... We compare this sum with a running minimum and update it if the new sum is smaller. The final result is the minimum value found after checking all n! permutations.

1class Solution {2    int minXorSum = Integer.MAX_VALUE;3    4    public int minimumXORSum(int[] nums1, int[] nums2) {5        permute(nums1, nums2, 0);6        return minXorSum;7    }8    9    private void permute(int[] nums1, int[] nums2, int index) {10        if (index == nums1.length) {11            int currentXorSum = 0;12            for (int i = 0; i < nums1.length; i++) {13                currentXorSum += nums1[i] ^ nums2[i];14            }15            minXorSum = Math.min(minXorSum, currentXorSum);16            return;17        }18        19        for (int i = index; i < nums2.length; i++) {20            swap(nums2, index, i);21            permute(nums1, nums2, index + 1);22            swap(nums2, index, i); // backtrack23        }24    }25    26    private void swap(int[] nums, int i, int j) {27        int temp = nums[i];28        nums[i] = nums[j];29        nums[j] = temp;30    }31}

• We define a recursive function, say solve(mask), which returns the minimum XOR sum possible.
• The mask is a bitmask where the j-th bit is set if nums2[j] has been used, and 0 otherwise.
• The number of set bits in the mask, i = Integer.bitCount(mask), tells us that we are trying to pair the i-th element of nums1, which is nums1[i].
• Base Case: If i == n (or mask has all n bits set), it means all elements from nums1 have been paired. The sum for the remaining (empty) set is 0, so we return 0.
• Memoization: We use an array, say memo, to store the results of solve(mask). If memo[mask] has already been computed, we return the stored value to avoid redundant calculations.
• Recursive Step:
  • Initialize a variable minSum to infinity.
  • Iterate through all elements of nums2 using an index j from 0 to n-1.
  • If nums2[j] is available (i.e., the j-th bit in mask is 0), we consider pairing nums1[i] with nums2[j].
  • The cost for this pairing is (nums1[i] ^ nums2[j]). We recursively call solve for the next state, where the mask is updated to include j: solve(mask | (1 << j)).
  • The total sum for this choice is (nums1[i] ^ nums2[j]) + solve(mask | (1 << j)). We update minSum with the minimum value found among all available choices of j.
• Finally, we store the computed minSum in memo[mask] and return it.
• The initial call to start the process is solve(0).

This approach uses dynamic programming with memoization (a top-down approach) to efficiently solve the problem by breaking it down into smaller, overlapping subproblems. The state of our DP can be defined by a bitmask. A mask of length n can represent the subset of elements from nums2 that have already been paired with elements from nums1.

Let solve(mask) be the minimum XOR sum we can get by pairing the remaining elements of nums1 with the unused elements of nums2. The mask indicates which indices of nums2 are already used. The number of set bits in mask tells us how many elements from nums1 (from index 0) have already been paired. For example, if k bits are set in mask, we are now considering pairing nums1[k].

We can implement this using a recursive function with a memoization table (an array, say memo) to store the results for each mask. This prevents re-computation for the same state, drastically reducing the time complexity compared to brute force.

Here is the top-down implementation with memoization:

1class Solution {2    int[] memo;3    int n;4    int[] nums1;5    int[] nums2;6 7    public int minimumXORSum(int[] nums1, int[] nums2) {8        this.n = nums1.length;9        this.nums1 = nums1;10        this.nums2 = nums2;11        this.memo = new int[1 << n];12        java.util.Arrays.fill(memo, -1);13        return solve(0);14    }15 16    private int solve(int mask) {17        if (mask == (1 << n) - 1) {18            return 0;19        }20        if (memo[mask] != -1) {21            return memo[mask];22        }23 24        int i = Integer.bitCount(mask); // Index for nums125        int minSum = Integer.MAX_VALUE;26 27        for (int j = 0; j < n; j++) {28            // If j-th element of nums2 is not used yet29            if ((mask & (1 << j)) == 0) {30                int currentSum = (nums1[i] ^ nums2[j]) + solve(mask | (1 << j));31                minSum = Math.min(minSum, currentSum);32            }33        }34 35        return memo[mask] = minSum;36    }37}

Alternatively, this can be solved using a bottom-up (iterative) DP approach, which often has slightly better performance by avoiding recursion overhead.

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