aboutsummaryrefslogtreecommitdiff
path: root/min_xor_sum_two_arr.py
blob: f54d44b8191a21f6593b0d08ebb49463f9e85307 (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

"""
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]))