Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n.
Follow up: Could you do this in O(n) runtime?
Example 1:
Input: nums = [3,10,5,25,2,8] Output: 28 Explanation: The maximum result is 5 XOR 25 = 28.
Example 2:
Input: nums = [0] Output: 0
Example 3:
Input: nums = [2,4] Output: 6
Example 4:
Input: nums = [8,10,2] Output: 10
Example 5:
Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70] Output: 127
Constraints:
1 <= nums.length <= 2 * 1040 <= nums[i] <= 231 - 1
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
max = 0
mask = 0
for i in range(30, -1, -1):
current = 1 << i
mask = mask ^ current
s = set()
for num in nums:
s.add(num & mask)
flag = max | current
for prefix in s:
if prefix ^ flag in s:
max = flag
break
return maxclass Trie:
def __init__(self):
self.left = None
self.right = None
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
self.root = Trie()
self.highest = 30
def add(num):
node = self.root
for i in range(self.highest, -1, -1):
bit = (num >> i) & 1
if bit == 0:
if node.left is None:
node.left = Trie()
node = node.left
else:
if node.right is None:
node.right = Trie()
node = node.right
def cal(num):
node = self.root
res = 0
for i in range(self.highest, -1, -1):
bit = (num >> i) & 1
if bit == 0:
if node.right:
res = res * 2 + 1
node = node.right
else:
res = res * 2
node = node.left
else:
if node.left:
res = res * 2 + 1
node = node.left
else:
res = res * 2
node = node.right
return res
res = 0
for i in range(1, len(nums)):
add(nums[i - 1])
res = max(res, cal(nums[i]))
return resclass Solution {
public int findMaximumXOR(int[] numbers) {
int max = 0;
int mask = 0;
for (int i = 30; i >= 0; i--) {
int current = 1 << i;
mask = mask ^ current;
Set<Integer> set = new HashSet<>();
for (int j = 0, k = numbers.length; j < k; j++) {
set.add(mask & numbers[j]);
}
int flag = max | current;
for (Integer prefix : set) {
if (set.contains(prefix ^ flag)) {
max = flag;
break;
}
}
}
return max;
}
}class Solution {
private static final int HIGHEST = 30;
private Trie root;
public int findMaximumXOR(int[] nums) {
int res = 0;
root = new Trie();
for (int i = 1; i < nums.length; ++i) {
add(nums[i - 1]);
res = Math.max(res, cal(nums[i]));
}
return res;
}
private int cal(int num) {
Trie node = root;
int res = 0;
for (int i = HIGHEST; i >= 0; --i) {
int bit = (num >> i) & 1;
if (bit == 0) {
if (node.right != null) {
res = res * 2 + 1;
node = node.right;
} else {
res = res * 2;
node = node.left;
}
} else {
if (node.left != null) {
res = res * 2 + 1;
node = node.left;
} else {
res = res * 2;
node = node.right;
}
}
}
return res;
}
private void add(int num) {
Trie node = root;
for (int i = HIGHEST; i >= 0; --i) {
int bit = (num >> i) & 1;
if (bit == 0) {
if (node.left == null) {
node.left = new Trie();
}
node = node.left;
} else {
if (node.right == null) {
node.right = new Trie();
}
node = node.right;
}
}
}
}
class Trie {
public Trie left;
public Trie right;
}class Trie {
public:
Trie* left;
Trie* right;
};
class Solution {
public:
int highest = 30;
Trie* root;
int findMaximumXOR(vector<int>& nums) {
root = new Trie();
int res = 0;
for (int i = 1; i < nums.size(); ++i)
{
add(nums[i - 1]);
res = max(res, cal(nums[i]));
}
return res;
}
int cal(int num) {
Trie* node = root;
int res = 0;
for (int i = highest; i >= 0; --i)
{
int bit = (num >> i) & 1;
if (bit == 0)
{
if (node->right)
{
res = res * 2 + 1;
node = node->right;
}
else
{
res = res * 2;
node = node->left;
}
}
else
{
if (node->left)
{
res = res * 2 + 1;
node = node->left;
}
else
{
res = res * 2;
node = node->right;
}
}
}
return res;
}
void add(int num) {
Trie* node = root;
for (int i = highest; i >= 0; --i)
{
int bit = (num >> i) & 1;
if (bit == 0)
{
if (!node->left) node->left = new Trie();
node = node->left;
}
else
{
if (!node->right) node->right = new Trie();
node = node->right;
}
}
}
};const highest = 30
type trie struct {
left, right *trie
}
func (root *trie) add(num int) {
node := root
for i := highest; i >= 0; i-- {
bit := (num >> i) & 1
if bit == 0 {
if node.left == nil {
node.left = &trie{}
}
node = node.left
} else {
if node.right == nil {
node.right = &trie{}
}
node = node.right
}
}
}
func (root *trie) cal(num int) int {
node := root
res := 0
for i := highest; i >= 0; i-- {
bit := (num >> i) & 1
if bit == 0 {
if node.right != nil {
res = res*2 + 1
node = node.right
} else {
res = res * 2
node = node.left
}
} else {
if node.left != nil {
res = res*2 + 1
node = node.left
} else {
res = res * 2
node = node.right
}
}
}
return res
}
func findMaximumXOR(nums []int) int {
root := &trie{}
res := 0
for i := 1; i < len(nums); i++ {
root.add(nums[i-1])
res = max(res, root.cal(nums[i]))
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}