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}