aboutsummaryrefslogtreecommitdiff
path: root/min_xor_sum_two_arr.c
blob: 492a0f8e60645afdebec3029b64bc87837f49879 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 1879. Minimum XOR Sum of Two Arrays
#include "leetcode.h"

/*
 * you are given two integer arrays 'nums1' and 'nums2' of length 'n'. the xor
 * sum of the two integer arrays is '(nums1[0] ^ nums2[0]) + (nums1[1] ^
 * nums2[1]) + ...' (0-indexed). rearrange the elements of 'nums2' such that
 * resulting xor sum is minimised. return the xor sum after the rearrangement.
 */

static int dp[1 << 14] = {[0 ... 16383] = INT_MAX};

int dfs(int *nums1, int *nums2, int n, int i, int mask) {
  if (i >= n)
    return 0;
  if (dp[mask] == -1)
    for (int j = 0; j < n; ++j)
      if (!(mask & (1 << j)))
        dp[mask] =
            fmin(dp[mask], (nums1[i] ^ nums2[j]) +
                               dfs(nums1, nums2, n, i + 1, mask + (1 << j)));
  return dp[mask];
}

int minimumXORSum(int *nums1, int nums1Size, int *nums2, int nums2Size) {
  return dfs(nums1, nums2, nums1Size, 0, 0);
}

int main() {
  int n11[] = {1, 2}, n21[] = {2, 3}, n12[] = {1, 0, 3}, n22[] = {5, 3, 4};
  printf("%d\n", minimumXORSum(n11, ARRAY_SIZE(n11), n21,
                               ARRAY_SIZE(n21))); // expect: 2
  printf("%d\n", minimumXORSum(n12, ARRAY_SIZE(n12), n22,
                               ARRAY_SIZE(n22))); // expect: 8
}