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

$ curl repovive.com/roadmaps/pattern-22/bit-manipulation/maximum-xor-of-two-numbers-implementation

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

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

$ curl repovive.com/roadmaps/pattern-22/bit-manipulation/maximum-xor-of-two-numbers-implementation

Repovive

LeetCode 421 Maximum XOR of Two Numbers - Implementation - Bit Manipulation | Pattern 22: LeetCode Interview Patterns | Repovive

Repovive.

Pattern 22: LeetCode Interview Patterns24 sections · 736 units32h total

Open in Course

LeetCode 421 Maximum XOR of Two Numbers - Implementation

The code

Trie-based approach for maximum XOR.

class TrieNode: def init(self): self.children = {}

def findMaximumXOR(nums): root = TrieNode() maxXor = 0

for num in nums:
    node = root
    xorNode = root
    currXor = 0
    for i in range(31, -1, -1):
        bit = (num >> i) & 1
        if bit not in node.children:
            node.children[bit] = TrieNode()
        node = node.children[bit]

        toggleBit = 1 - bit
        if toggleBit in xorNode.children:
            currXor = (currXor << 1) | 1
            xorNode = xorNode.children[toggleBit]
        else:
            currXor = currXor << 1
            xorNode = xorNode.children.get(bit, xorNode)
    maxXor = max(maxXor, currXor)

return maxXor

$O(32n)$ time, $O(32n)$ space.