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 = [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 * 10^50 <= nums[i] <= 2^31 - 1
The description was taken from https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/.
#O(N) Time, O(1) Space where N is Key Lengthclass TreeNode: def __init__(self, val) -> None: self.val = val self.children = {} class Solution: def __init__(self): self.root = TreeNode(None) def insert(self, num:int) -> None: curr_node = self.root num = bin(num)[2:].zfill(32) for bit in num: if bit not in curr_node.children: curr_node.children[bit] = TreeNode(bit) curr_node = curr_node.children[bit] def search_xor(self, num: int) -> int: binary = bin(num)[2:].zfill(32) want, prefix = None, [] curr_node = self.root for bit in binary: if bit == "0": want = "1" elif bit == "1": want = "0" if want in curr_node.children: prefix.append(want) curr_node = curr_node.children[want] else: prefix.append(bit) curr_node = curr_node.children[bit] prefix = int("".join(prefix), 2) return prefix ^ num def findMaximumXOR(self, nums: List[int]) -> int: max_xor = 0 for num in nums: self.insert(num) for num in nums: max_xor = max(max_xor, self.search_xor(num)) return max_xorIf we were to look at a truth table for an XOR, it would look like this.
| Input | Output | |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
We can see that to get a favorable output, we would want to have opposing bits. To utilize this information, we will want to build up a list of prefixes that we can traverse and within each index, we will look for the opposing bit from one number to the current number. If we find a number with that opposing bit in its prefix, we will want to make that number our new choice to battle against the current.
With that information in mind, a good way to traverse prefixes is with a Prefix Tree, also known as a Trie.
We can insert each number into the Trie, then traverse each number at the same time with linear time required since they will share similar prefixes. That way, we can also save space.
Let's start by defining our TrieNode class.
Each Trie node will contain a bit value to identify itself and a hashmap of children Trie nodes.
class TrieNode: def __init__(self, val) -> None: self.val = val self.children = {}
Now we can start building our solution.
class Solution:
We will initialize a root Trie node during our solution. We don't want to give it value yet because we don't know what the first bit will be at this point. We will instead set it as a dummy node.
def __init__(self): self.root = TrieNode(None)
Next, we will want to create an insert function to place each binary versioned number into the Trie.
This function will take a number as an input. We will want to left-pad the binary version of the number with zeros so that they can all be the same number of digits, otherwise, we will get false XORs later when we have some numbers that have more leading zeros than others, since converting them to binary won't automatically do this for us.
def insert(self, num:int) -> None: curr_node = self.root num = bin(num)[2:].zfill(32)
Next, we will insert each bit into the trie, only making a new Trienode when we get to a differing bit that isn't already shared with the prefixes in the Trie.
for bit in num: if bit not in curr_node.children: curr_node.children[bit] = TreeNode(bit)
Meaning, if we already have 1011, and our number is 1010, our trie will look like this:
With the introduction of the new bit to the prefix.
We will then either iterate to the bit that we just made or the bit we didn't have to make because it was already in the prefix.
curr_node = curr_node.children[bit]
Now let's make our function to search the Trie for an opposing prefix to the current number input.
def search_xor(self, num: int) -> int:
The goal of this function is to build up the best prefix available, given what is in our tree.
We will start by converting our number to binary and left-padding it with zeros as we did previously.
binary = bin(num)[2:].zfill(32)
Then, we will create a want variable that we will continuously set to the opposing bit from the current, and a prefix list to hold the best prefix we could muster up so far.
want, prefix = None, []
We will then make a curr_node iterator and begin our traversal.
curr_node = self.root
For each bit in the binary number, we will calculate the opposing bit one by one and see if a number exists with it in the Trie.
If it does, we will append that opposing bit to the output and continue down the prefix branch that has the opposing bit.
If not, we will just do the same for the current bit, since we weren't able to get the one we wanted if it is not in the Trie.
for bit in binary: if bit == "0": want = "1" elif bit == "1": want = "0" if want in curr_node.children: prefix.append(want) curr_node = curr_node.children[want] else: prefix.append(bit) curr_node = curr_node.children[bit]
At the end of our traversal, we will convert the best opposing prefix we found and convert it back into a binary number.
prefix = int("".join(prefix), 2)
Then, we will return the XOR of the prefix with the current number.
return prefix ^ num
Now we just have to utilize these functions to get our answer.
def findMaximumXOR(self, nums: List[int]) -> int:
We will initialize our max_xor value, then we will insert each number into the Trie.
max_xor = 0 for num in nums: self.insert(num) for num in nums: max_xor = max(max_xor, self.search_xor(num)) return max_xor