diff options
-rw-r--r-- | min_xor_sum_two_arr.c | 35 | ||||
-rw-r--r-- | 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 new file mode 100644 index 0000000..492a0f8 --- /dev/null +++ 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 new file mode 100644 index 0000000..f54d44b --- /dev/null +++ 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])) |