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.lengthn == nums2.length1 <= n <= 140 <= nums1[i], nums2[i] <= 107
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
| 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]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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#
1
2
3
4
5
6
7
8
9
10
11
| 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]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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#
1
2
3
4
5
6
7
8
9
10
11
| 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]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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;
}
|
