leetcode

commit bf408cd8346c296ee1960a6a1a03fe1270296e49
parent 88adbcc57a22112c6e45c61d3b1b77f315066b87
Author: Jack Sangdahl <jack@pngu.org>
Date:   Tue, 25 Mar 2025 11:44:59 -0600

1879. minimum xor sum of two arrays

Diffstat:
A
min_xor_sum_two_arr.c
 | 
35
+++++++++++++++++++++++++++++++++++
A
min_xor_sum_two_arr.py
 | 
35
+++++++++++++++++++++++++++++++++++

2 files changed, 70 insertions(+), 0 deletions(-)
diff --git a/min_xor_sum_two_arr.c b/min_xor_sum_two_arr.c
@@ -0,0 +1,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
+}
diff --git a/min_xor_sum_two_arr.py b/min_xor_sum_two_arr.py
@@ -0,0 +1,35 @@
+# 1879. Minimum XOR Sum of Two Arrays
+
+"""
+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.
+"""
+
+
+class Solution(object):
+    def minimumXORSum(self, nums1, nums2):
+        """
+        :type nums1: List[int]
+        :type nums2: List[int]
+        :rtype: int
+        """
+
+        def dfs(mask):
+            i = bin(mask).count("1")
+            if i >= len(nums1):
+                return 0
+            return min(
+                (nums1[i] ^ nums2[j]) + dfs(mask + (1 << j))
+                for j in range(len(nums2))
+                if mask & (1 << j) == 0
+            )
+
+        return dfs(0)
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.minimumXORSum(nums1=[1, 2], nums2=[2, 3]))
+    print(obj.minimumXORSum(nums1=[1, 0, 3], nums2=[5, 3, 4]))