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
139
140
141
142
143
144
145
|
#ifdef LOCAL
#include <bits/stdc++.h>
using namespace std;
// tree node stuff here...
#endif
static int __initialSetup = []()
{
std::ios::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}
();
const int N = 500000;
struct Node {
int left, right;
void init()
{
left = -1;
right = -1;
}
};
struct Trie {
Node nodes[N];
int nextAvailable;
void init()
{
nodes[0].init();
nextAvailable = 1;
}
vector<int> toBinary(int x)
{
vector<int> ans(32, 0);
for (int i = 0; i < 32; i++)
ans[i] = (x >> i) & 1;
reverse(ans.begin(), ans.end()); // so now [0] is MSB
return ans;
}
int toInteger(vector<int> &num)
{
reverse(num.begin(), num.end());
int ans = 0;
for (int i = 0; i < 32; i++)
if (num[i] == 1)
ans |= (1 << i);
return ans;
}
void insert(const vector<int> &num)
{
int pos = 0;
for (int i = 0; i < 32; i++) {
if (num[i] == 0) {
if (nodes[pos].left == -1) {
nodes[nextAvailable].init();
nodes[pos].left = nextAvailable++;
}
pos = nodes[pos].left;
} else {
if (nodes[pos].right == -1) {
nodes[nextAvailable].init();
nodes[pos].right = nextAvailable++;
}
pos = nodes[pos].right;
}
}
}
void insert(int x)
{
auto num = toBinary(x);
insert(num);
}
vector<int> search(const vector<int> &num)
{
vector<int> ans;
int pos = 0;
for (int i = 0; i < 32; i++) {
if (num[i] == 0) {
if (nodes[pos].right == -1) {
ans.push_back(0);
pos = nodes[pos].left;
} else {
pos = nodes[pos].right;
ans.push_back(1);
}
} else {
if (nodes[pos].left == -1) {
ans.push_back(1);
pos = nodes[pos].right;
} else {
pos = nodes[pos].left;
ans.push_back(0);
}
}
}
return ans;
}
int search(int x)
{
// look for the most mismatched number
auto num = toBinary(x);
auto res = search(num);
return toInteger(res);
}
};
class Solution
{
public:
int findMaximumXOR(vector<int> &nums)
{
// observation
// let's look at the numbers in their binary representation
// starting from the MSB (leftmost) bit
// for every number, we look for the most mismatched number
// thus we can get the max value of them all
// trie!
int mx = 0;
Trie trie;
trie.init();
for (auto i : nums) {
trie.insert(i);
mx = max(mx, i ^ trie.search(i));
}
return mx;
}
};
#ifdef LOCAL
int main()
{
return 0;
}
#endif
|