# Minimum XOR Sum of Two Arrays
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-xor-sum-of-two-arrays)
Canonical: https://scaleengineer.com/dsa/problems/minimum-xor-sum-of-two-arrays
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
**Companies:** [Media.net](https://scaleengineer.com/companies/media.net)
---
## 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 _the **XOR sum** after the rearrangement_.

**Example 1:**

**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:**

**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] <= 107`

# Approaches
## Brute Force using Permutations
The most straightforward way to solve the problem is to try every possible arrangement of `nums2`. Since we can rearrange `nums2` in any way, this corresponds to finding the best permutation of `nums2` that, when paired element-wise with `nums1`, yields the minimum possible XOR sum. We can generate all `n!` permutations of `nums2`, calculate the XOR sum for each, and find the minimum among them.
**Time:** O(n * n!) - There are `n!` possible permutations of `nums2`. For each permutation, we take O(n) time to calculate the XOR sum. Thus, the total time complexity is `n * n!`. · **Space:** O(n) - The space complexity is determined by the depth of the recursion stack for generating permutations, which is `n`.
**Pros:** Conceptually simple and easy to understand.; Correct for very small values of `n`.
**Cons:** Extremely inefficient due to its factorial time complexity.; Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints (n <= 14).
### Explanation
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.

```java
class Solution {
    int minXorSum = Integer.MAX_VALUE;
    
    public int minimumXORSum(int[] nums1, int[] nums2) {
        permute(nums1, nums2, 0);
        return minXorSum;
    }
    
    private void permute(int[] nums1, int[] nums2, int index) {
        if (index == nums1.length) {
            int currentXorSum = 0;
            for (int i = 0; i < nums1.length; i++) {
                currentXorSum += nums1[i] ^ nums2[i];
            }
            minXorSum = Math.min(minXorSum, currentXorSum);
            return;
        }
        
        for (int i = index; i < nums2.length; i++) {
            swap(nums2, index, i);
            permute(nums1, nums2, index + 1);
            swap(nums2, index, i); // backtrack
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```
### Algorithm
- 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.

## Dynamic Programming with Bitmasking
Given the constraint `n <= 14`, a solution with exponential time complexity in `n`, such as `O(n * 2^n)`, is feasible. This hints towards a Dynamic Programming approach using bitmasking. This problem can be framed as an assignment problem: assign each element of `nums1` to a unique element of `nums2` to minimize the total cost (XOR sum). We can use a bitmask to represent the set of used elements from `nums2`, and DP to solve the subproblems of assigning the first `k` elements of `nums1` to a subset of `k` elements from `nums2`.
**Time:** O(n * 2^n) - There are `2^n` possible masks (states). For each state, we iterate through `n` elements of `nums2` to decide the next pairing. Therefore, the total time complexity is `n * 2^n`. · **Space:** O(2^n) - We need a memoization table or a DP array of size `2^n` to store the results for all possible masks. The recursion stack for the top-down approach adds an `O(n)` factor, but `O(2^n)` dominates.
**Pros:** Significantly more efficient than the brute-force approach.; Guaranteed to find the optimal solution within the time limits for the given constraints.; It is a standard and powerful technique for solving assignment-type problems with small constraints.
**Cons:** The exponential time and space complexity makes it infeasible for larger `n` (e.g., n > 20).; Requires understanding of bit manipulation and dynamic programming concepts.
### Explanation
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:
```java
class Solution {
    int[] memo;
    int n;
    int[] nums1;
    int[] nums2;

    public int minimumXORSum(int[] nums1, int[] nums2) {
        this.n = nums1.length;
        this.nums1 = nums1;
        this.nums2 = nums2;
        this.memo = new int[1 << n];
        java.util.Arrays.fill(memo, -1);
        return solve(0);
    }

    private int solve(int mask) {
        if (mask == (1 << n) - 1) {
            return 0;
        }
        if (memo[mask] != -1) {
            return memo[mask];
        }

        int i = Integer.bitCount(mask); // Index for nums1
        int minSum = Integer.MAX_VALUE;

        for (int j = 0; j < n; j++) {
            // If j-th element of nums2 is not used yet
            if ((mask & (1 << j)) == 0) {
                int currentSum = (nums1[i] ^ nums2[j]) + solve(mask | (1 << j));
                minSum = Math.min(minSum, currentSum);
            }
        }

        return memo[mask] = minSum;
    }
}
```
Alternatively, this can be solved using a bottom-up (iterative) DP approach, which often has slightly better performance by avoiding recursion overhead.
```java
class Solution {
    public int minimumXORSum(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] dp = new int[1 << n];
        java.util.Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int mask = 1; mask < (1 << n); mask++) {
            int k = Integer.bitCount(mask);
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0) {
                    int prevMask = mask ^ (1 << j);
                    if (dp[prevMask] != Integer.MAX_VALUE) {
                        dp[mask] = Math.min(dp[mask], dp[prevMask] + (nums1[k - 1] ^ nums2[j]));
                    }
                }
            }
        }
        return dp[(1 << n) - 1];
    }
}
```
### Algorithm
- 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)`.

# Solutions
### Java

```java
class Solution {
public
  int minimumXORSum(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int[][] f = new int[n + 1][1 << n];
    for (var g : f) {
      Arrays.fill(g, 1 << 30);
    }
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < 1 << n; ++j) {
        for (int k = 0; k < n; ++k) {
          if ((j >> k & 1) == 1) {
            f[i][j] = Math.min(f[i][j], f[i - 1][j ^ (1 << k)] +
                                            (nums1[i - 1] ^ nums2[k]));
          }
        }
      }
    }
    return f[n][(1 << n) - 1];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumXORSum(vector<int> &nums1, vector<int> &nums2) {
    int n = nums1.size();
    int f[n + 1][1 << n];
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < 1 << n; ++j) {
        for (int k = 0; k < n; ++k) {
          if (j >> k & 1) {
            f[i][j] = min(f[i][j],
                          f[i - 1][j ^ (1 << k)] + (nums1[i - 1] ^ nums2[k]));
          }
        }
      }
    }
    return f[n][(1 << n) - 1];
  }
};

```

### Python

```python
class Solution:
    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int: n = len(nums2) f = [[inf] * (1 << n) for _ in range(n + 1)] f[0][0] = 0 for i, x in enumerate(nums1, 1): for j in range(1 << n): for k in range(n): if j >> k & 1: f[i][j] = min(f[i][j], f[i - 1][j ^ (1 << k)] + (x ^ nums2[k])) return f[- 1][- 1]

```