Skip to main content

1879. Minimum XOR Sum of Two Arrays

This page provides solutions for the leetcode problem 1879. Minimum XOR Sum of Two Arrays.

Problem Explanation

The problem is asking us to minimize the XOR of two input array nums1\text{nums}1 and nums2\text{nums}2, given that you can rearrange elements of nums2\text{nums2}.

Solution

This problem can be solved using the Permutations technique. More such questions can be found here.

import java.util.HashMap;

class Solution {
private HashMap<Integer, Integer> memo;

public int minimumXORSum(int[] nums1, int[] nums2) {
memo = new HashMap<>();
int res = permute(nums1, nums2, 0, 0);
return res;
}

private int permute(int[] nums1, int[] nums2, int index, int mask) {
if(memo.containsKey(mask)) return memo.get(mask);
if(index == nums2.length) return 0;
else {
int ans = Integer.MAX_VALUE;
for(int i = 0; i < nums2.length; i++) {
if(((mask >> i) & 1) == 1) continue;
int internalAns = (nums1[index] ^ nums2[i]) + permute(
nums1, nums2, index + 1, mask | (1 << i)
);
ans = Math.min(ans, internalAns);
}
memo.put(mask, ans);
return ans;
}
}
}
info

In this solution we have avoided redundant computations by adding memoization.

Consider if we've chosen the 00th and 11st elements from input array num2{\text{num2}}, and then again

Complexity

Let's say there are N\text{N} elements in an array, and we need to create K\text{K} subsets.

Time Complexity

The time complexity is O(2N)\text{O}(2^{\text{N}}) for creating a single subset, as we can either choose or skip each element of an array, and O(K)\text{O}(\text{K}) for creating K\text{K} subsets, so total time complexity will be:

O(K2N)\text{O}(\text{K} * 2^{\text{N}})

Space Complexity

At any given time, the excution stack will have at most N\text{N} elements, so total space complexity will be:

O(N)\text{O}(\text{N})