Bitwise Trie

Instead of characters, each edge is a bit (0 or 1). Insert numbers from MSB to LSB. To maximize XOR with a number, at each bit position, try to go the opposite direction (to set that XOR bit to 1).

Algorithm

// Insert: walk MSB to LSB
for bit = 30 down to 0:
  b = (num >> bit) & 1
  go to child[b], create if needed

// Query: maximize XOR
for bit = 30 down to 0:
  b = (num >> bit) & 1
  want = 1 - b // opposite!
  if child[want] exists: go there
  else: go child[b]

Interactive Visualization

Current Number

Chosen Path

Best XOR Pair

Array:

Array (with binary)

Step 0 of 0

Processing

—

Best Partner

—

XOR

Max XOR

Ready. Press Play or Next to start.

✓ Done

Speed

C++ — Maximum XOR with Bitwise Trie

struct BitNode { BitNode* ch[2] = {}; };

void insert(BitNode* root, int num) {
    BitNode* node = root;
    for (int i = 30; i >= 0; i--) {
        int bit = (num >> i) & 1;
        if (!node->ch[bit])
            node->ch[bit] = new BitNode();
        node = node->ch[bit];
    }
}

int maxXorWith(BitNode* root, int num) {
    BitNode* node = root;
    int xorVal = 0;
    for (int i = 30; i >= 0; i--) {
        int bit = (num >> i) & 1;
        int want = 1 - bit; // opposite
        if (node->ch[want]) {
            xorVal |= (1 << i);
            node = node->ch[want];
        } else {
            node = node->ch[bit];
        }
    }
    return xorVal;
}

int findMaximumXOR(vector<int>& nums) {
    BitNode* root = new BitNode();
    int maxXor = 0;
    for (int num : nums) {
        insert(root, num);
        maxXor = max(maxXor, maxXorWith(root, num));
    }
    return maxXor;
}

Complexity

Time

O(N × 31)

Insert + query for each of N numbers, 31 bits each.

Space

O(N × 31)

At most N×31 nodes in the trie.

📝 Notes

▼