1879. Minimum XOR Sum of Tw...

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 $\text{nums}1$ and $\text{nums}2$, given that you can rearrange elements of $\text{nums2}$.

Solution

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

Java

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++) {
                // Skip if the bit at position i in the mask is already set
                if (((mask >> i) & 1) == 1) {
                    continue;
                }

                // Calculate internal answer using XOR and recursion
                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 $0$^th and $1$^st elements from input array ${\text{num2}}$, and then again

Complexity

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

Time Complexity

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

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

Space Complexity

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

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