Last active
December 5, 2016 15:31
-
-
Save KirillLykov/d427a8d6fa84482f87ad3317cf4a1d49 to your computer and use it in GitHub Desktop.
Problem 421 from leetcode, O(n) solution using Trie
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
struct Node { | |
Node(): left(nullptr), right(nullptr) {} | |
shared_ptr<Node> left, right; | |
}; | |
typedef shared_ptr<Node> NodePtr; | |
shared_ptr<Node> root; | |
void add(int v) { | |
NodePtr n = root; | |
for (int i = 31; i >= 0; --i) { | |
if ( ((v>>i)&1) == 1 ) { | |
if (n->right == nullptr) | |
n->right.reset(new Node); | |
n = n->right; | |
} else { | |
if (n->left == nullptr) | |
n->left.reset(new Node); | |
n = n->left; | |
} | |
} | |
} | |
int findDifferent(int v) { | |
int res = 0; | |
NodePtr n = root; | |
for (int i = 31; i >= 0; --i) { | |
if ( ((v>>i)&1) == 1 ) { | |
if ( n->left != nullptr ) { | |
n = n->left; | |
} else { | |
n = n->right; | |
res |= 1 << i; | |
} | |
} else { | |
if ( n->right != nullptr ) { | |
n = n->right; | |
res |= 1 << i; | |
} else { | |
n = n->left; | |
} | |
} | |
} | |
return res; | |
} | |
int findMaximumXOR(vector<int>& nums) { | |
root.reset(new Node); | |
for (int v : nums) { | |
add(v); | |
} | |
int maxsofar = 0; | |
for (int v : nums) { | |
maxsofar = max(maxsofar, v^findDifferent(v)); | |
} | |
return maxsofar; | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment