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

$ curl repovive.com/roadmaps/data-structures/tries/maximum-xor-solution

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████

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

$ curl repovive.com/roadmaps/data-structures/tries/maximum-xor-solution

Repovive

Maximum XOR Solution - Tries | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Maximum XOR Solution

Implement your solution

def findMaximumXOR(nums):
 root = TrieNode()

 # Insert all numbers
 for num in nums:
 node = root
 for i in range(31, -1, -1):
 bit = (num >> i) & 1
 if not node.children[bit]:
 node.children[bit] = TrieNode()
 node = node.children[bit]

 # Find max XOR for each number
 maxXor = 0
 for num in nums:
 node = root
 xor = 0
 for i in range(31, -1, -1):
 bit = (num >> i) & 1
 opp = 1 - bit
 if node.children[opp]:
 xor |= (1 << i)
 node = node.children[opp]
 else:
 node = node.children[bit]
 maxXor = max(maxXor, xor)

 return maxXor

Time: $O(32n) = O(n)$ . Space: $O(32n) = O(n)$ for trie.