1879. Minimum XOR Sum of Two Arrays

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

Example: 2

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

Output: 8

Constraints:

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

Thought process:

• We can come to a solution just by permuting all elements in nums2 array and then individually calculating the result for all cases and then finding the minimum amongst them.
• But this will have O(N!) * N complexity which will be too much for n = 14.
• But the thing we can clearly see is that the order of elements in nums2 matters if we want to get a minimum answer.
• So, it becomes mandatory for us to try all possible orders or pairings, so that, our result must be minimum.
• At time like this, when we have to try all possible orders, yet, it cannot be achieved in time constraints, we can think of DP as our best bet.
• This is because at such times, trying all possible orders is inevitable, but, we might be making some calculations again and again, which causes us to get TLE if solved naively.
• So we will solve this problem using DP.

Explanation of algorithm:

• Let's say we are at index 0 of nums1. We can pair it up with 0th, 1st, ..., nth element of nums2 array. This forms our XOR1.
• Then we go to index 1 and out of all unpaired elements in nums2 we select any element and pair it up with index 1 of nums1. This forms our XOR2.
• But how will we know which elements have been paired and which are not paired? For this we will use bit-masking.
• Suppose, we have selected 5th element in nums2. Then we will mark this taken element in our integer number using bitmasking.
• This is done by mask = mask | (1 << 5). So to mark the ith element as taken, all we need to do is : mask = mask | (1 << i)
• In this way we will mark all the taken and non-taken elements so far.

Solving using recursion:

• Now we will proceed in the manner explained above recursively.
• This is shown in the code below.

Naive implementation using only recursion (will give TLE): class Solution { public int minimumXORSum(int[] nums1, int[] nums2) { // initially no elements were taken // so used = 0 return recur(0, 0, nums1, nums2); } int recur(int idx, int used, int[] nums1, int[] nums2) { // if all elements are taken // we will return 0 if(idx >= nums1.length) { return 0; } int min = Integer.MAX_VALUE; for(int i = 0; i < nums1.length; i++) { // we are pairing the nums2[i] with nums1[idx] int xor = nums1[idx] ^ nums2[i]; int newUsed = used | (1 << i); // if used == newUsed, this means that we are only taking the element which was taken into another pair // so, we ignore this and continue to search for the next pairing if(used == newUsed) { continue; } // if we found perfect pair // we will mark this element as taken and proceed further recursively min = Math.min(min, xor + recur(idx + 1, newUsed, nums1, nums2)); } return min; } }

Changing TLE to Accepted (Using Caching):

• Now we can see clearly that many subproblems are solved multiple times.
• This results into TLE.
• So we will store the results in an array based on the function's index and taken elements value.
• So we won't be computing the results for each subproblem over and over again.
• Also it is important to note that, we can select any elements at anytime. So the number of taken elements will be all possible combinations of N elements viz (2 ^ N).

Full Code (Java): class Solution { public int minimumXORSum(int[] nums1, int[] nums2) { Integer[][] dp = new Integer[nums1.length + 1][1 << 15]; return recur(0, 0, nums1, nums2, dp); } int recur(int idx, int used, int[] nums1, int[] nums2, Integer[][] dp) { if(idx >= nums1.length) { return 0; } // checking if the current subproblem is solved or not // if yes, the result will be given immediately // if no, it will be stored after solving the subproblem if(dp[idx][used] != null) { return dp[idx][used]; } int min = Integer.MAX_VALUE; for(int i = 0; i < nums1.length; i++) { int xor = nums1[idx] ^ nums2[i]; int newUsed = used | (1 << i); if(used == newUsed) { continue; } min = Math.min(min, xor + recur(idx + 1, newUsed, nums1, nums2, dp)); } // storing value in dp array to reduce re-computations dp[idx][used] = min; return min; } }