Skip to main content
Back to problems
#1879
Hard Algorithms

Minimum xor sum of two arrays

Array Dynamic Programming Bit Manipulation Bitmask
50.6% acceptance
Feb 25, 2026
717
13
You are given two integer arrays nums1 and nums2 of length n. Rearrange the elements of nums2 to minimize the XOR sum (nums1[0] XOR nums2[0]) + ... + (nums1[n-1] XOR nums2[n-1]). Return the XOR sum after the rearrangement.

Solution

Rust
Time O(n²)
Space O(n)
LeetCode
solution.rs 
impl Solution {
  pub fn minimum_xor_sum(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
    let n = nums1.len();
    let full = 1usize << n;
    let mut dp = vec![i32::MAX; full];
    dp[0] = 0;

    for mask in 0..full {
      if dp[mask] == i32::MAX { continue; }
      let j = mask.count_ones() as usize; // next index in nums1
      if j >= n { continue; }
      for i in 0..n {
        if mask & (1 << i) == 0 {
          let next = mask | (1 << i);
          let cost = nums1[j] ^ nums2[i];
          if dp[mask] + cost < dp[next] {
            dp[next] = dp[mask] + cost;
          }
        }
      }
    }

    dp[full - 1]
  }
}