Question

1879. Minimum XOR Sum of Two Arrays

中文文档

Description

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_.

 

Example 1:

Input: nums1 = [1,2], nums2 = [2,3]
Output: 2
Explanation: Rearrange nums2 so that it becomes [3,2].
The XOR sum is (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.

Example 2:

Input: nums1 = [1,0,3], nums2 = [5,3,4]
Output: 8
Explanation: Rearrange nums2 so that it becomes [5,4,3]. 
The XOR sum is (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8.

 

Constraints:

• n == nums1.length
• n == nums2.length
• 1 <= n <= 14
• 0 <= nums1[i], nums2[i] <= 107

Solutions

Solution 1

class Solution:
  def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
    n = len(nums2)
    f = [[inf] * (1 << n) for _ in range(n + 1)]
    f[0][0] = 0
    for i, x in enumerate(nums1, 1):
      for j in range(1 << n):
        for k in range(n):
          if j >> k & 1:
            f[i][j] = min(f[i][j], f[i - 1][j ^ (1 << k)] + (x ^ nums2[k]))
    return f[-1][-1]

class Solution {
  public int minimumXORSum(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int[][] f = new int[n + 1][1 << n];
    for (var g : f) {
      Arrays.fill(g, 1 << 30);
    }
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < 1 << n; ++j) {
        for (int k = 0; k < n; ++k) {
          if ((j >> k & 1) == 1) {
            f[i][j]
              = Math.min(f[i][j], f[i - 1][j ^ (1 << k)] + (nums1[i - 1] ^ nums2[k]));
          }
        }
      }
    }
    return f[n][(1 << n) - 1];
  }
}

class Solution {
public:
  int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
    int n = nums1.size();
    int f[n + 1][1 << n];
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < 1 << n; ++j) {
        for (int k = 0; k < n; ++k) {
          if (j >> k & 1) {
            f[i][j] = min(f[i][j], f[i - 1][j ^ (1 << k)] + (nums1[i - 1] ^ nums2[k]));
          }
        }
      }
    }
    return f[n][(1 << n) - 1];
  }
};

func minimumXORSum(nums1 []int, nums2 []int) int {
  n := len(nums1)
  f := make([][]int, n+1)
  for i := range f {
    f[i] = make([]int, 1<<n)
    for j := range f[i] {
      f[i][j] = 1 << 30
    }
  }
  f[0][0] = 0
  for i := 1; i <= n; i++ {
    for j := 0; j < 1<<n; j++ {
      for k := 0; k < n; k++ {
        if j>>k&1 == 1 {
          f[i][j] = min(f[i][j], f[i-1][j^(1<<k)]+(nums1[i-1]^nums2[k]))
        }
      }
    }
  }
  return f[n][(1<<n)-1]
}

function minimumXORSum(nums1: number[], nums2: number[]): number {
  const n = nums1.length;
  const f: number[][] = Array(n + 1)
    .fill(0)
    .map(() => Array(1 << n).fill(1 << 30));
  f[0][0] = 0;
  for (let i = 1; i <= n; ++i) {
    for (let j = 0; j < 1 << n; ++j) {
      for (let k = 0; k < n; ++k) {
        if (((j >> k) & 1) === 1) {
          f[i][j] = Math.min(f[i][j], f[i - 1][j ^ (1 << k)] + (nums1[i - 1] ^ nums2[k]));
        }
      }
    }
  }
  return f[n][(1 << n) - 1];
}

Solution 2

class Solution:
  def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
    n = len(nums2)
    f = [inf] * (1 << n)
    f[0] = 0
    for x in nums1:
      for j in range((1 << n) - 1, -1, -1):
        for k in range(n):
          if j >> k & 1:
            f[j] = min(f[j], f[j ^ (1 << k)] + (x ^ nums2[k]))
    return f[-1]

class Solution {
  public int minimumXORSum(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int[] f = new int[1 << n];
    Arrays.fill(f, 1 << 30);
    f[0] = 0;
    for (int x : nums1) {
      for (int j = (1 << n) - 1; j >= 0; --j) {
        for (int k = 0; k < n; ++k) {
          if ((j >> k & 1) == 1) {
            f[j] = Math.min(f[j], f[j ^ (1 << k)] + (x ^ nums2[k]));
          }
        }
      }
    }
    return f[(1 << n) - 1];
  }
}

class Solution {
public:
  int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
    int n = nums1.size();
    int f[1 << n];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int x : nums1) {
      for (int j = (1 << n) - 1; ~j; --j) {
        for (int k = 0; k < n; ++k) {
          if (j >> k & 1) {
            f[j] = min(f[j], f[j ^ (1 << k)] + (x ^ nums2[k]));
          }
        }
      }
    }
    return f[(1 << n) - 1];
  }
};

func minimumXORSum(nums1 []int, nums2 []int) int {
  n := len(nums1)
  f := make([]int, 1<<n)
  for i := range f {
    f[i] = 1 << 30
  }
  f[0] = 0
  for _, x := range nums1 {
    for j := (1 << n) - 1; j >= 0; j-- {
      for k := 0; k < n; k++ {
        if j>>k&1 == 1 {
          f[j] = min(f[j], f[j^(1<<k)]+(x^nums2[k]))
        }
      }
    }
  }
  return f[(1<<n)-1]
}

function minimumXORSum(nums1: number[], nums2: number[]): number {
  const n = nums1.length;
  const f: number[] = Array(1 << n).fill(1 << 30);
  f[0] = 0;
  for (const x of nums1) {
    for (let j = (1 << n) - 1; ~j; --j) {
      for (let k = 0; k < n; ++k) {
        if (((j >> k) & 1) === 1) {
          f[j] = Math.min(f[j], f[j ^ (1 << k)] + (x ^ nums2[k]));
        }
      }
    }
  }
  return f[(1 << n) - 1];
}

Solution 3

class Solution:
  def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
    n = len(nums2)
    f = [inf] * (1 << n)
    f[0] = 0
    for i in range(1, 1 << n):
      k = i.bit_count() - 1
      for j in range(n):
        if i >> j & 1:
          f[i] = min(f[i], f[i ^ (1 << j)] + (nums1[k] ^ nums2[j]))
    return f[-1]

class Solution {
  public int minimumXORSum(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int[] f = new int[1 << n];
    Arrays.fill(f, 1 << 30);
    f[0] = 0;
    for (int i = 0; i < 1 << n; ++i) {
      int k = Integer.bitCount(i) - 1;
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 1) {
          f[i] = Math.min(f[i], f[i ^ (1 << j)] + (nums1[k] ^ nums2[j]));
        }
      }
    }
    return f[(1 << n) - 1];
  }
}

class Solution {
public:
  int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
    int n = nums1.size();
    int f[1 << n];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 0; i < 1 << n; ++i) {
      int k = __builtin_popcount(i) - 1;
      for (int j = 0; j < n; ++j) {
        if (i >> j & 1) {
          f[i] = min(f[i], f[i ^ (1 << j)] + (nums1[k] ^ nums2[j]));
        }
      }
    }
    return f[(1 << n) - 1];
  }
};

func minimumXORSum(nums1 []int, nums2 []int) int {
  n := len(nums1)
  f := make([]int, 1<<n)
  for i := range f {
    f[i] = 1 << 30
  }
  f[0] = 0
  for i := 0; i < 1<<n; i++ {
    k := bits.OnesCount(uint(i)) - 1
    for j := 0; j < n; j++ {
      if i>>j&1 == 1 {
        f[i] = min(f[i], f[i^1<<j]+(nums1[k]^nums2[j]))
      }
    }
  }
  return f[(1<<n)-1]
}

function minimumXORSum(nums1: number[], nums2: number[]): number {
  const n = nums1.length;
  const f: number[] = Array(1 << n).fill(1 << 30);
  f[0] = 0;
  for (let i = 0; i < 1 << n; ++i) {
    const k = bitCount(i) - 1;
    for (let j = 0; j < n; ++j) {
      if (((i >> j) & 1) === 1) {
        f[i] = Math.min(f[i], f[i ^ (1 << j)] + (nums1[k] ^ nums2[j]));
      }
    }
  }
  return f[(1 << n) - 1];
}

function bitCount(i: number): number {
  i = i - ((i >>> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
  i = (i + (i >>> 4)) & 0x0f0f0f0f;
  i = i + (i >>> 8);
  i = i + (i >>> 16);
  return i & 0x3f;
}