/
maximum-strong-pair-xor-ii.py
138 lines (125 loc) · 4.78 KB
/
maximum-strong-pair-xor-ii.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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
# Time: O(nlogn + nlogr) = O(nlogr), r = max(nums)
# Space: O(t)
# bit manipulation, greedy, trie, sort, two pointers
class Solution(object):
def maximumStrongPairXor(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
class Trie(object):
def __init__(self, bit_length):
self.__nodes = []
self.__cnts = []
self.__new_node()
self.__bit_length = bit_length
def __new_node(self):
self.__nodes.append([-1]*2)
self.__cnts.append(0)
return len(self.__nodes)-1
def update(self, num, d):
curr = 0
for i in reversed(xrange(self.__bit_length)):
x = num>>i
if self.__nodes[curr][x&1] == -1:
self.__nodes[curr][x&1] = self.__new_node()
curr = self.__nodes[curr][x&1]
self.__cnts[curr] += d
def query(self, num):
result = curr = 0
for i in reversed(xrange(self.__bit_length)):
result <<= 1
x = num>>i
if self.__nodes[curr][1^(x&1)] != -1 and self.__cnts[self.__nodes[curr][1^(x&1)]]:
curr = self.__nodes[curr][1^(x&1)]
result |= 1
else:
curr = self.__nodes[curr][x&1]
return result
nums.sort()
trie = Trie(nums[-1].bit_length())
result = j = 0
for i, num in enumerate(nums):
trie.update(num, +1)
while not (nums[i] <= 2*nums[j]) :
trie.update(nums[j], -1)
j += 1
result = max(result, trie.query(num))
return result
# Time: O(nlogr), r = max(nums)
# Space: O(t)
# bit manipulation, greedy, trie, dp
class Solution2(object):
def maximumStrongPairXor(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
class Trie(object):
def __init__(self, bit_length):
self.__nodes = []
self.__mins = []
self.__maxs = []
self.__new_node()
self.__bit_length = bit_length
def __new_node(self):
self.__nodes.append([-1]*2)
self.__mins.append(float("inf"))
self.__maxs.append(float("-inf"))
return len(self.__nodes)-1
def insert(self, num):
curr = 0
for i in reversed(xrange(self.__bit_length)):
x = num>>i
if self.__nodes[curr][x&1] == -1:
self.__nodes[curr][x&1] = self.__new_node()
curr = self.__nodes[curr][x&1]
self.__mins[curr] = min(self.__mins[curr], num)
self.__maxs[curr] = max(self.__maxs[curr], num)
def query(self, num):
result = curr = 0
for i in reversed(xrange(self.__bit_length)):
result <<= 1
x = num>>i
y = (result|1)^x
assert(x != y)
if (self.__nodes[curr][y&1] != -1 and
((x > y and num <= 2*self.__maxs[self.__nodes[curr][y&1]]) or
(x < y and self.__mins[self.__nodes[curr][y&1]] <= 2*num))):
result |= 1
curr = self.__nodes[curr][y&1]
else:
curr = self.__nodes[curr][1^(y&1)]
return result
trie = Trie(max(nums).bit_length())
result = 0
for num in nums:
trie.insert(num)
result = max(result, trie.query(num))
return result
# Time: O(nlogr), r = max(nums)
# Space: O(n)
# bit manipulation, greedy, dp
class Solution3(object):
def maximumStrongPairXor(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
result = 0
for i in reversed(xrange(max(nums).bit_length())):
prefix_min, prefix_max = {}, {}
for x in nums:
y = x>>i
if y not in prefix_min:
prefix_min[y] = prefix_max[y] = x
prefix_min[y] = min(prefix_min[y], x)
prefix_max[y] = max(prefix_max[y], x)
result <<= 1
for x in prefix_min.iterkeys():
y = (result|1)^x
assert(x != y)
if y in prefix_max and prefix_min[max(x, y)] <= 2*prefix_max[min(x, y)]:
result |= 1
break
return result