Minimum XOR Sum of Two Arrays - Practice Coding Problems

Minimum XOR Sum of Two Arrays - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [1,2], nums2 = [2,3]

› Output: 2

💡 Note: Rearrange nums2 to [3,2]. XOR sum = (1^3) + (2^2) = 2 + 0 = 2, which is minimum

Example 2 — Three Elements

$ Input: nums1 = [1,2,3], nums2 = [1,2,3]

› Output: 0

💡 Note: Keep nums2 as [1,2,3]. XOR sum = (1^1) + (2^2) + (3^3) = 0 + 0 + 0 = 0

Example 3 — No Perfect Match

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

› Output: 8

💡 Note: Rearrange nums2 to [5,4,3]. XOR sum = (1^5) + (0^4) + (3^3) = 4 + 4 + 0 = 8

Constraints

n == nums1.length
n == nums2.length
1 ≤ n ≤ 14
0 ≤ nums1[i], nums2[i] ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two arrays nums1 and nums2 of equal length

Rearrange nums2

Find optimal permutation of nums2 to minimize XOR sum

Calculate Result

Sum of XOR operations between corresponding elements

Key Takeaway

🎯 Key Insight: This is an assignment problem where we must find the optimal one-to-one pairing between elements to minimize total cost

Asked in

G Google 15 M Microsoft 12 a Amazon 8

This is a classic assignment problem that requires finding the optimal pairing between elements of two arrays to minimize the total XOR sum. The key insight is that each element in nums2 can only be used once, making it impossible to use greedy approaches. The optimal solution uses dynamic programming with bitmasks to efficiently explore all possible assignments. Time: O(n² × 2ⁿ), Space: O(n × 2ⁿ)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Permutations	O(n! × n)	O(n)	Generate all possible permutations of nums2 and find the one with minimum XOR sum
Dynamic Programming with Bitmask	O(n² × 2ⁿ)	O(n × 2ⁿ)	Use bitmask DP to track which elements from nums2 have been used

Brute Force - Try All Permutations — Algorithm Steps

Generate all permutations of nums2
For each permutation, calculate XOR sum with nums1
Track and return the minimum sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible arrangements of nums2

Calculate XOR Sum

For each permutation, compute XOR sum with nums1

Find Minimum

Track and return the smallest XOR sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int minXorSum = INT_MAX;

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void permute(int* nums1, int* nums2, int n, int start) {
    if (start == n) {
        int currentSum = 0;
        for (int i = 0; i < n; i++) {
            currentSum += nums1[i] ^ nums2[i];
        }
        if (currentSum < minXorSum) {
            minXorSum = currentSum;
        }
        return;
    }
    
    for (int i = start; i < n; i++) {
        swap(&nums2[start], &nums2[i]);
        permute(nums1, nums2, n, start + 1);
        swap(&nums2[start], &nums2[i]);
    }
}

int solution(int* nums1, int* nums2, int n) {
    minXorSum = INT_MAX;
    permute(nums1, nums2, n, 0);
    return minXorSum;
}

int main() {
    int nums1[20], nums2[20];
    int n = 0;
    char line[1000];
    
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums1[n++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int m = 0;
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[],\n");
    while (token != NULL) {
        nums2[m++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(nums1, nums2, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

Generate n! permutations, each taking O(n) time to calculate XOR sum

⚠ Quadratic Growth

Space Complexity

O(n)

Space for storing one permutation and recursion stack

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler