The O(n) Club: Maximum XOR of Two Numbers in an Array: Ditch Loops, Grab Bits

The O(n) Club: Maximum XOR of Two Numbers in an Array: Ditch Loops, Grab Bits

⚡ TL;DR

Find the biggest XOR between any two numbers in an array? Don’t brute force unless you like coffee jitters and timeouts. Use prefix sets and bit-smarts for O(n) glory.

// Brute force: please don't
int maxXor = 0;
for (int i = 0; i < nums.length; i++) {
  for (int j = i + 1; j < nums.length; j++) {
    maxXor = Math.max(maxXor, nums[i] ^ nums[j]);
  }
}

🧠 How Devs Usually Mess This Up

The classic slip: everyone whips out two nested loops, tests all the pairs, and bravely waits for their laptop fans to start levitating. That’s O(n²) purgatory, and Interviewer just marked you as “must train from zero.” Also, no, sorting doesn’t help. XOR is bit drama, not number order. And please, recognize that XOR (unlike sum/AND/OR) wants different bits per position. 1 ^ 1 = 0. That’s its thing!

🔍 What’s Actually Going On

Here’s the plot twist: the biggest XOR comes from numbers that disagree furthest to the left in their bit masks. So, instead of clumsy pair-checking, peel off bits from left to right, building the answer one bit at a time. At each step, toss all prefixes (numbers chopped to current bit) into a set. Like a detective with amnesia, ask: “Does any pair of these prefixes let me flip this bit to 1?” If yes, keep the bit, drop the mic, move to the next. If not, that bit stays dark. No drama, no double-for loops, just clean bitwise moves.

🛠️ PseudoCode

• max = 0: Initialize. Because empty variables blow up sneakily.
• For each bit from 31 to 0: Start with the highest (leftmost, James Bond tier).

  for (int bit = 31; bit >= 0; bit--) {
      // Build up one bit at a time
  }

• Slap all number prefixes up to this bit into a set.

  Set<Integer> prefixes = new HashSet<>();
  for (int num : nums) {
      prefixes.add(num >>> bit);
  }

  Chop the numbers, lose the right bits. Just keep the left.
• Guess the new max: flip this bit ON.

  int testMax = (max << 1) | 1;

• Can a pair of prefixes XOR to testMax? Just check if testMax ^ prefix is also in the set. If yes, upgrade max. If no, forget this bit.

  for (int prefix : prefixes) {
      if (prefixes.contains(testMax ^ prefix)) {
          max = testMax;
          break;
      }
  }

💻 The Code

// O(n) with bit-magic
public int findMaximumXOR(int[] nums) {
    int max = 0;
    for (int bit = 31; bit >= 0; bit--) {
        Set<Integer> prefixes = new HashSet<>();
        for (int num : nums) {
            prefixes.add(num >>> bit);
        }
        int testMax = (max << 1) | 1;
        boolean rocked = false;
        for (int prefix : prefixes) {
            if (prefixes.contains(testMax ^ prefix)) {
                max = testMax;
                rocked = true;
                break;
            }
        }
        if (!rocked)
            max = testMax - 1;
    }
    return max;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Don’t let XOR become sum, AND, or wishful thinking. 1 ^ 1 == 0. XO, XO!
• n² won’t save you—LeetCode will eat your RAM for a snack.
• Sorting? Please. Even QuickSort is rolling its eyes here.
• Use >>> (unsigned shift) or negative numbers will make you cry into your stack trace.
• Time: O(32n) (just call it linear). Space: O(n). Interviewer is relieved.

🧠 Interviewer Brain-Tattoo

“Bitwise wins: the only time you’re rewarded for arguing with yourself one bit at a time.”