The O(n) Club: Missing Number — How to Outsmart That One Number Who Didn’t RSVP

The O(n) Club: Missing Number — How to Outsmart That One Number Who Didn’t RSVP

⚡ TL;DR

One number from to n ditched your array — everyone else showed up. Don’t sort. Don’t panic. XOR or a sneaky sum both solve it in O(n):

// Bad brute force: RSVP policing committee
for (int i = 0; i <= n; i++) {
    boolean found = false;
    for (int num : nums) {
        if (num == i) { found = true; break; }
    }
    if (!found) return i;
}
// Efficient as a phonebook lookup in a blackout.

🧠 How Devs Usually Mess This Up

When you see find the missing number you may be tempted to sort the whole mess, set up a hash table, or go full overkill. Please don’t. Sorting is pointless (“But my merge sort!”) and extra memory is just you showing off your RAM budget. Nested loops? That’s pure sabotage — this isn’t the 90s and Java can go fast now. Most who slip up either double-check everything or assume the problem is sneakier than advertised (spoiler: it isn’t).

🔍 What’s Actually Going On

Imagine you’re throwing a party for n+1 numbers, but one didn’t text back. Old-school way: add up who was supposed to come and who actually did, difference is the slacker. Or, skip the math and let XOR magic do the sorting — every legit guest cancels out, only the missing VIP remains. Think of it as musical chairs for numbers: someone’s left standing, and XOR sees it instantly.

🛠️ PseudoCode

• Initialize your detective: int xor = n; (covering the full expected range)
• Loop through the clues: For i = 0 to n - 1, xor ^= i ^ nums[i];
• Done. Return the survivor: return xor; (the one that bailed on your party)
• Or, for the arithmetic squad:
  – Calculate expectedSum = n * (n + 1) / 2
  – Scan the array to get actualSum
  – Return expectedSum - actualSum

💻 The Code

// XOR all the numbers, all the indices
public int missingNumber(int[] nums) {
    int xor = nums.length;
    for (int i = 0; i < nums.length; i++) {
        xor ^= i ^ nums[i];
    }
    return xor;
}
 // Nerdy math method
public int missingNumberSum(int[] nums) {
    int n = nums.length;
    int expected = n * (n + 1) / 2;
    int actual = 0;
    for (int v : nums) actual += v;
    return expected - actual;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• If you initialize xor with 0 not n, say goodbye to catching n as the missing number. Been there. Laughed at that bug report.
• Sorting wastes O(n log n), which is like heating your house by burning cash. Don’t.
• The sum trick will overflow if n is huge. Java will smile and give you the wrong answer — it’s polite like that.
• This only works if all numbers are unique and exactly one is missing. If you find duplicates or multiple disappearances, grab another problem.
• Both approaches are O(n) time and O(1) space. Anything worse is a tech debt time bomb.

🧠 Interviewer Brain-Tattoo

“In XOR land, everyone brings a date. Only the missing number goes home alone.” If your solution needs a hashmap, the numbers are silently judging you.