Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtrie

Maximum XOR of Two Numbers in an Array

Problem (restated)

Given non-negative integers, return the maximum value of nums[i] XOR nums[j] (i may equal j).

Intuition

Build a binary trie of bits MSB→LSB. For each number, greedily walk opposite bits to maximize XOR.

Approaches

Binary bit trie

Unverified

Time O(32n)Space O(32n)

Idea. Insert then query (self-XOR is 0; better pairs appear after insert of both). Prefer opposite bit at each level.

Walkthrough. [3,10,5,25,2,8] → 28 (5 XOR 25).

Trade-offs. O(n^2) brute is fine for tiny n; trie is O(n) with 32-bit width.

Solution

type Node = { 0?: Node; 1?: Node };

export function findMaximumXOR(nums: number[]): number {
  const root: Node = {};
  const insert = (x: number) => {
    let n = root;
    for (let b = 31; b >= 0; b--) {
      const bit = ((x >> b) & 1) as 0 | 1;
      n[bit] ??= {};
      n = n[bit]!;
    }
  };
  const query = (x: number): number => {
    let n = root;
    let best = 0;
    for (let b = 31; b >= 0; b--) {
      const bit = (x >> b) & 1;
      const want = (1 - bit) as 0 | 1;
      if (n[want]) {
        best |= 1 << b;
        n = n[want]!;
      } else {
        n = n[bit as 0 | 1]!;
      }
    }
    return best;
  };
  let ans = 0;
  for (const x of nums) {
    insert(x);
    ans = Math.max(ans, query(x));
  }
  return ans;
}

type Node = { 0?: Node; 1?: Node };

export function findMaximumXOR(nums: number[]): number {
  const root: Node = {};
  const insert = (x: number) => {
    let n = root;
    for (let b = 31; b >= 0; b--) {
      const bit = ((x >> b) & 1) as 0 | 1;
      n[bit] ??= {};
      n = n[bit]!;
    }
  };
  const query = (x: number): number => {
    let n = root;
    let best = 0;
    for (let b = 31; b >= 0; b--) {
      const bit = (x >> b) & 1;
      const want = (1 - bit) as 0 | 1;
      if (n[want]) {
        best |= 1 << b;
        n = n[want]!;
      } else {
        n = n[bit as 0 | 1]!;
      }
    }
    return best;
  };
  let ans = 0;
  for (const x of nums) {
    insert(x);
    ans = Math.max(ans, query(x));
  }
  return ans;
}

Template connection

Trie over bit strings for greedy XOR.

Reflection

Bit trie, high bit first. For each number take the opposite bit when it exists, otherwise the bit that is present. The XOR is those choices.
Stay inside 31 positive bits. Folding in the sign bit changes the result.
One number is 0. Two equal numbers are 0. All zeros answer 0.