forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
minimum-xor-sum-of-two-arrays.py
72 lines (68 loc) · 2.56 KB
/
minimum-xor-sum-of-two-arrays.py
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# Time: O(n^3)
# Space: O(n^2)
# weighted bipartite matching solution
class Solution(object):
def minimumXORSum(self, nums1, nums2):
# Template translated from:
# https://github.com/kth-competitive-programming/kactl/blob/main/content/graph/WeightedMatching.h
def hungarian(a): # Time: O(n^2 * m), Space: O(n + m)
if not a:
return 0, []
n, m = len(a)+1, len(a[0])+1
u, v, p, ans = [0]*n, [0]*m, [0]*m, [0]*(n-1)
for i in xrange(1, n):
p[0] = i
j0 = 0 # add "dummy" worker 0
dist, pre = [float("inf")]*m, [-1]*m
done = [False]*(m+1)
while True: # dijkstra
done[j0] = True
i0, j1, delta = p[j0], None, float("inf")
for j in xrange(1, m):
if done[j]:
continue
cur = a[i0-1][j-1]-u[i0]-v[j]
if cur < dist[j]:
dist[j], pre[j] = cur, j0
if dist[j] < delta:
delta, j1 = dist[j], j
for j in xrange(m):
if done[j]:
u[p[j]] += delta
v[j] -= delta
else:
dist[j] -= delta
j0 = j1
if not p[j0]:
break
while j0: # update alternating path
j1 = pre[j0]
p[j0], j0 = p[j1], j1
for j in xrange(1, m):
if p[j]:
ans[p[j]-1] = j-1
return -v[0], ans # min cost
adj = [[0]*len(nums2) for _ in xrange(len(nums1))]
for i in xrange(len(nums1)):
for j in xrange(len(nums2)):
adj[i][j] = nums1[i]^nums2[j]
return hungarian(adj)[0]
# Time: O(n * 2^n)
# Space: O(2^n)
# dp solution
class Solution2(object):
def minimumXORSum(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: int
"""
dp = [(float("inf"), float("inf"))]*(2**len(nums2))
dp[0] = (0, 0)
for mask in xrange(len(dp)):
bit = 1
for i in xrange(len(nums2)):
if (mask&bit) == 0:
dp[mask|bit] = min(dp[mask|bit], (dp[mask][0]+(nums1[dp[mask][1]]^nums2[i]), dp[mask][1]+1))
bit <<= 1
return dp[-1][0]