2Brute2Best
🔥0
03

Bitwise trie (Trie Sub-pattern)

Store numbers as bit paths, highest bit first. To maximise a XOR, walk down preferring the opposite bit at each level.

Signals in the problem statement
  • ›

    "maximum XOR of two numbers"

  • ›

    "maximum XOR with an element not exceeding m"

What makes it different

Maximum XOR of Two Numbers inserts every number and queries each one against the trie: O(31 · n) instead of O(n²). Maximum XOR With an Element adds a limit m per query. Answer the queries offline: sort the queries by m and the numbers ascending, insert numbers up to m just before each query, and return −1 when the trie is still empty.

Questions

ordered from “learn the idea” to “recognise it without help”
  1. 1
    Maximum XOR of Two Numbers in an Array
    Basic Anchor·LeetCode #421
    Medium
  2. 2
    Maximum XOR With an Element From Array
    Interview-Level·LeetCode #1707
    Hard

Template

bitwise-trie-template.cpp
// Bitwise trie: store each number's bits from the highest down.
// For the largest XOR with x, prefer the OPPOSITE bit at every level: one higher bit
// is worth more than all lower bits together (2^b > 2^b - 1).
struct BitNode {
    BitNode* child[2] = {};
};

const int HIGH = 30;                          // values < 2^31

void insert(BitNode* root, int x) {
    BitNode* cur = root;
    for (int b = HIGH; b >= 0; b--) {
        int bit = (x >> b) & 1;
        if (!cur->child[bit]) cur->child[bit] = new BitNode();
        cur = cur->child[bit];
    }
}

// Largest x XOR y over all y in the trie (the trie must not be empty).
int bestXor(BitNode* root, int x) {
    BitNode* cur = root;
    int result = 0;
    for (int b = HIGH; b >= 0; b--) {
        int want = 1 - ((x >> b) & 1);        // the bit that makes this XOR bit 1
        if (cur->child[want]) { result |= 1 << b; cur = cur->child[want]; }
        else cur = cur->child[1 - want];
    }
    return result;
}
Remember this · Trie
Trigger
Many words + prefix search, autocomplete, word dictionary with wildcards, maximum XOR.
Think
Do many queries share prefixes that I keep re-checking?
Key question
What does each node store (children, end-of-word, count)?
Trie + DFS search