# 421. Maximum XOR of Two Numbers in an Array

Maximum XOR of Two Numbers in an Array - LeetCode

Given an integer array nums, return __the maximum result of __nums[i] XOR nums[j], where 0 <= i <= j < n.

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 = [14,70,53,83,49,91,36,80,92,51,66,70] Output: 127

Constraints:

1 <= nums.length <= 2 * 105 0 <= nums[i] <= 231 - 1

• code
``````class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
# Compute length L of max number in a binary representation
L = len(bin(max(nums))) - 2
# zero left-padding to ensure L bits for each number
nums = [[(x >> i) & 1 for i in range(L)][::-1] for x in nums]

max_xor = 0
trie = {}
for num in nums:
node = trie
xor_node = trie
curr_xor = 0
for bit in num:
# insert new number in trie
if not bit in node:
node[bit] = {}
node = node[bit]

# to compute max xor of that new number
# with all previously inserted
toggled_bit = 1 - bit
if toggled_bit in xor_node:
curr_xor = (curr_xor << 1) | 1
xor_node = xor_node[toggled_bit]
else:
curr_xor = curr_xor << 1
xor_node = xor_node[bit]

max_xor = max(max_xor, curr_xor)

return max_xor
``````
• code #trie
``````class TrieNode {
TrieNode[] children;
public TrieNode() {
children = new TrieNode[2];
}
}

class Solution {
public int findMaximumXOR(int[] nums) {
if (null == nums || 0 == nums.length)
return 0;

// get the longest binary representation.
int maxLen = 0;
for (int x : nums)
maxLen = Math.max(maxLen, Integer.toBinaryString(x).length());

// construct binary representation for each number.
String[] strs = new String[nums.length];
int padding = (1 << maxLen);
for (int i = 0; i < nums.length; ++i)

// construct trie first, and then get the max from the trie.
TrieNode root = new TrieNode();
for (String x : strs) {
TrieNode curr = root;
for (char c : x.toCharArray()) {
int bit = c - '0';
if (null == curr.children[bit])
curr.children[bit] = new TrieNode();
curr = curr.children[bit];
}
}

int result = 0;
for (String x : strs) {
TrieNode curr = root;
int currRes = 0;
for (char c : x.toCharArray()) {
int bit = c - '0';
if (null != curr.children[1 - bit]) {
currRes = (currRes << 1) | 1;
curr = curr.children[1 - bit];
} else {
currRes <<= 1;
curr = curr.children[bit];
}
}

result = Math.max(result, currRes);
}

return result;
}
}
``````
• code
``````class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
length = len(bin(max(nums))) - 2 # 0bxxx
res = cur = 0
for i in reversed(range(length)):
res <<= 1
cur = res | 1
prefix = {num >> i for num in nums}
for p in prefix:
if cur ^ p in prefix:
res = cur
break
return res
``````