##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/421.html

# 421. Maximum XOR of Two Numbers in an Array (Medium)

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 * 104
• 0 <= nums[i] <= 231 - 1

Related Topics:
Bit Manipulation, Trie

## Solution 1. Trie

Flatten the bits information of the array into a Trie. For each number in array, use Trie to find the maximum value it can get using xor.

// OJ: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
// Time: O(N)
// Space: O(1)
// Ref: https://discuss.leetcode.com/topic/63207/java-o-n-solution-using-trie
struct TrieNode {
TrieNode *next[2] = {};
};
class Solution {
void addNode(TrieNode *node, int n) {
for (int i = 31; i >= 0; --i) {
int bit = (n >> i) & 1;
if (!node->next[bit]) node->next[bit] = new TrieNode();
node = node->next[bit];
}
}
public:
int findMaximumXOR(vector<int>& A) {
TrieNode root;
for (int n : A) addNode(&root, n);
int ans = 0;
for (int n : A) {
auto node = &root;
int val = 0;
for (int i = 31; i >= 0; --i) {
int bit = (n >> i) & 1;
if (node->next[1 ^ bit]) {
val |= 1 << i;
node = node->next[1 ^ bit];
} else node = node->next[bit];
}
ans = max(ans, val);
}
return ans;
}
};


## Solution 2.

// OJ: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
// Time: O(N)
// Space: O(N)
// Ref: https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap
class Solution {
public:
int findMaximumXOR(vector<int>& A) {
unordered_set<int> s;
int mask = 0, ans = 0;
for (int i = 31; i >= 0; --i) {
mask |= 1 << i;
s.clear();
for (int n : A) s.insert(n & mask);
int next = ans | (1 << i);
for (int prefix : s) {
if (!s.count(next ^ prefix)) continue;
ans |= 1 << i;
break;
}
}
return ans;
}
};

• class Solution {
public int findMaximumXOR(int[] nums) {
int xor = 0;
int mask = 0;
for (int i = 31; i >= 0; i--) {
mask |= (1 << i);
Set<Integer> prefixSet = new HashSet<Integer>();
for (int num : nums)
int temp = xor | (1 << i);
for (int prefix : prefixSet) {
if (prefixSet.contains(prefix ^ temp)) {
xor = temp;
break;
}
}
}
return xor;
}
}

############

class Solution {

public int findMaximumXOR(int[] numbers) {
int max = 0;
int mask = 0;
for (int i = 30; i >= 0; i--) {
int current = 1 << i;
Set<Integer> set = new HashSet<>();
for (int j = 0, k = numbers.length; j < k; j++) {
}
int flag = max | current;
for (Integer prefix : set) {
if (set.contains(prefix ^ flag)) {
max = flag;
break;
}
}
}
return max;
}
}


• // OJ: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
// Time: O(N)
// Space: O(1)
// Ref: https://discuss.leetcode.com/topic/63207/java-o-n-solution-using-trie
struct TrieNode {
TrieNode *next[2] = {};
};
class Solution {
void add(TrieNode *node, int n) {
for (int i = 31; i >= 0; --i) {
int b = n >> i & 1;
if (node->next[b] == NULL) node->next[b] = new TrieNode();
node = node->next[b];
}
}
int maxXor(TrieNode *node, int n) {
int ans = 0;
for (int i = 31; i >= 0; --i) {
int b = n >> i & 1;
if (node->next[1 - b]) { // if we can go the opposite direction, do it.
node = node->next[1 - b];
ans |= 1 << i;
} else {
node = node->next[b];
}
}
return ans;
}
public:
int findMaximumXOR(vector<int>& A) {
TrieNode root;
int ans = 0;
for (int n : A) {
ans = max(ans, maxXor(&root, n));
}
return ans;
}
};

• class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
max = 0
for i in range(30, -1, -1):
current = 1 << i
s = set()
for num in nums:
flag = max | current
for prefix in s:
if prefix ^ flag in s:
max = flag
break
return max

############

class TrieNode(object):
def __init__(self, bit=None):
self.isWord = False
self.word = None
self.one = None
self.zero = None

count = 0

class Solution(object):
def findMaximumXOR(self, nums):
"""
:type nums: List[int]
:rtype: int
"""

def dfs(root, num, mask):
if not root:
return
if mask == 0x00:
self.ans = max(self.ans, root.word ^ num)
return
if mask & num:
if root.zero:
dfs(root.zero, num, mask >> 1)
else:
dfs(root.one, num, mask >> 1)
else:
if root.one:
dfs(root.one, num, mask >> 1)
else:
dfs(root.zero, num, mask >> 1)

if len(nums) < 2:
return 0
root = TrieNode()
self.ans = float("-inf")
for num in nums:
p = root
for i in range(0, 32):
node = None
if num & mask:
if not p.one:
node = TrieNode()
p.one = node
else:
node = p.one
else:
if not p.zero:
node = TrieNode()
p.zero = node
else:
node = p.zero
p = node
p.isWord = True
p.word = num
for num in nums:
dfs(root, num, 0x80000000)
return self.ans


• type Trie struct {
children [26]*Trie
}

func newTrie() *Trie {
return &Trie{}
}

func (this *Trie) insert(x int) {
node := this
for i := 30; i >= 0; i-- {
v := (x >> i) & 1
if node.children[v] == nil {
node.children[v] = newTrie()
}
node = node.children[v]
}
}

func (this *Trie) search(x int) int {
node := this
res := 0
for i := 30; i >= 0; i-- {
v := (x >> i) & 1
if node.children[v^1] != nil {
res = res<<1 | 1
node = node.children[v^1]
} else {
res <<= 1
node = node.children[v]
}
}
return res
}

func findMaximumXOR(nums []int) int {
trie := newTrie()
ans := 0
for _, v := range nums {
trie.insert(v)
ans = max(ans, trie.search(v))
}
return ans
}

func max(a, b int) int {
if a > b {
return a
}
return b
}