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

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

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

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

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

Repovive

Maximum XOR of Two Numbers - Implementation - Bit Manipulation | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Maximum XOR of Two Numbers - Implementation

Here is the implementation using a trie:

class TrieNode:
    children = [null, null]  // 0 and 1

function findMaximumXOR(nums):
    root = new TrieNode()

    // Insert all numbers
    for num in nums:
        node = root
        for i from 31 down to 0:
            bit = (num >> i) & 1
            if node.children[bit] == null:
                node.children[bit] = new TrieNode()
            node = node.children[bit]

    maxXor = 0
    for num in nums:
        node = root
        currentXor = 0
        for i from 31 down to 0:
            bit = (num >> i) & 1
            oppositeBit = 1 - bit
            if node.children[oppositeBit] != null:
                currentXor |= (1 << i)
                node = node.children[oppositeBit]
            else:
                node = node.children[bit]
        maxXor = max(maxXor, currentXor)

    return maxXor

$O(32n) = O(n)$ time, $O(32n)$ space for trie.