# 1879. Minimum XOR Sum of Two Arrays

• Time: $O(2^n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: int minimumXORSum(vector& nums1, vector& nums2) { return dfs(nums1, nums2, vector(1 << nums2.size(), INT_MAX), 0, 0); } private: int dfs(const vector& A, const vector& B, vector&& dp, int i, int mask) { if (i == A.size()) return 0; if (dp[mask] < INT_MAX) return dp[mask]; for (int j = 0; j < B.size(); ++j) if (!(mask >> j & 1)) dp[mask] = min(dp[mask], (A[i] ^ B[j]) + dfs(A, B, move(dp), i + 1, mask | 1 << j)); return dp[mask]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int minimumXORSum(int[] nums1, int[] nums2) { int[] dp = new int[1 << nums2.length]; Arrays.fill(dp, Integer.MAX_VALUE); return dfs(nums1, nums2, dp, 0, 0); } private int dfs(int[] A, int[] B, int[] dp, int i, int mask) { if (i == A.length) return 0; if (dp[mask] < Integer.MAX_VALUE) return dp[mask]; for (int j = 0; j < B.length; ++j) if ((mask >> j & 1) == 0) dp[mask] = Math.min(dp[mask], (A[i] ^ B[j]) + dfs(A, B, dp, i + 1, mask | 1 << j)); return dp[mask]; } } 
  1 2 3 4 5 6 7 8 9 10 class Solution: def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int: @functools.lru_cache(None) def dp(mask: int) -> int: i = bin(mask).count("1") if i == len(nums1): return 0 return min((nums1[i] ^ nums2[j]) + dp(mask | 1 << j) for j in range(len(nums2)) if not mask >> j & 1) return dp(0)