D
DevExCode

LeetCode 1879: Minimum XOR Sum of Two Arrays Solution

Master LeetCode problem 1879 (Minimum XOR Sum of Two Arrays), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1879. Minimum XOR Sum of Two Arrays

Hard
ArrayDynamic ProgrammingBit ManipulationBitmask

Problem Explanation

Explanation

To minimize the XOR sum, we need to pair the elements from nums1 and nums2 in a way that the XOR sum is minimized. This problem can be solved using dynamic programming with bitmasking.

  1. Dynamic Programming with Bitmasking:

    • We can represent a state as dp[mask][i], where mask is a bitmask representing the elements used from nums2 and i represents the index in nums1.
    • Initialize dp[mask][i] with a large value and set dp[0][0] to 0.
    • Iterate over all possible masks and for each mask, iterate over all elements in nums2.
    • For each mask and element in nums2, update dp[mask | (1 << j)][i + 1] with the minimum of current dp value and dp[mask][i] + (nums1[i] XOR nums2[j]).
    • The final answer will be dp[(1 << n) - 1][n], where n is the size of nums1 and nums2.

  2. Time Complexity:

    • The time complexity is O(n^3 * 2^n), where n is the size of nums1 and nums2.

  3. Space Complexity:

    • The space complexity is O(n * 2^n).

Solution Code

class Solution {
    public int minimumXORSum(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[][] dp = new int[1 << n][n];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dp[0][0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if ((mask & (1 << j)) == 0) {
                        int newMask = mask | (1 << j);
                        dp[newMask][i + 1] = Math.min(dp[newMask][i + 1], dp[mask][i] + (nums1[i] ^ nums2[j]));
                    }
                }
            }
        }
        
        return dp[(1 << n) - 1][n];
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1879 (Minimum XOR Sum of Two Arrays)?

This page provides optimized solutions for LeetCode problem 1879 (Minimum XOR Sum of Two Arrays) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1879 (Minimum XOR Sum of Two Arrays)?

The time complexity for LeetCode 1879 (Minimum XOR Sum of Two Arrays) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1879 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1879 in Java, C++, or Python.

Back to LeetCode Solutions