The Missing Number: Three Ways to Crack a Classic Interview Question

A 5-second interview moment

When I joined my current company, the CEO interviewed me personally. At some point he leaned back and posed a puzzle:

“You have an array of numbers from 1 to 100, unsorted, but one number is missing. How would you find it?”

I’d never seen this problem before. But within about 3–5 seconds, something clicked — a clean little shortcut that felt almost too simple to be correct. I gave him my answer.

He paused, and in a thinking-but-slightly-surprised tone said “Okay… interesting…” — which I’ll happily take as a win. 😄

What surprised me was how efficient the trick turned out to be. Later I asked several friends the same question, and almost all of them reached first for a different, much more “obvious” approach. That contrast is exactly what makes this problem worth writing about — it’s a small puzzle that quietly rewards you for thinking in math instead of loops.

So let’s walk through it properly: the instinctive solution, the one I stumbled onto, a beautiful bitwise trick, and where each one breaks down.

---

The problem, stated precisely

You’re given an array containing the numbers 1 to n (here n = 100), in no particular order, with exactly one value missing. Find the missing value.

We’ll judge each solution on three things: time complexity, space complexity, and how gracefully it generalizes.

---

Approach 1: The “seen” array (the intuitive first instinct)

This is what most people reach for first, and it’s a perfectly reasonable instinct. Keep a second array of booleans. Walk the input once, marking each number as seen. Then walk the boolean array and report whichever index was never marked.

def find_missing_seen(arr, n=100):
    seen = [False] * (n + 1)   # indices 0..n; we ignore index 0
    for x in arr:
        seen[x] = True
    for i in range(1, n + 1):
        if not seen[i]:
            return i

Why it works: every present number flips its slot to True. The one slot still False is the gap.

• Time: O(n) — two linear passes.
• Space: O(n) — the extra boolean array.

---

Approach 2: The sum formula (Gauss to the rescue)

This is the one — the shortcut that clicked in those few seconds and earned that “okay… interesting…” from the CEO. Here’s the idea.

There’s a famous (probably apocryphal) story that a young Carl Friedrich Gauss, asked to add the numbers 1 to 100 as busywork, produced the answer almost instantly using the formula:

Sum of 1 to n = n(n + 1) / 2

For n = 100, that’s 100 × 101 / 2 = 5050.

So the expected total is fixed and known. Add up the numbers that are actually present, subtract from the expected total, and the leftover is the missing number.

def find_missing_sum(arr, n=100):
    expected = n * (n + 1) // 2   # 5050 when n = 100
    return expected - sum(arr)

• Time: O(n) — a single pass to sum the array.
• Space: O(1) — just one running total.

That’s the same time as the seen-array approach but with constant extra space, and it doesn’t depend on the array being sorted.

---

Approach 3: The XOR trick (bit magic)

This is the one I didn’t think of on my own, and it’s genuinely elegant. It relies on the exclusive-or (^) operator. XOR compares two bits and returns 1 only when the bits differ:

A	B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

From that little table, three magical properties fall out:

1. a ^ a = 0 — anything XOR’d with itself cancels to zero (every bit matches, so every result bit is 0).
2. a ^ 0 = a — XOR with zero leaves a number unchanged.
3. XOR is commutative and associative — order doesn’t matter; you can shuffle the operands freely.

Put those together and a plan appears: XOR every number from 1 to n, then XOR in every number actually present in the array. Each number that is present now appears twice in the combined pile — once from the full range, once from the array — so it cancels itself to zero. The missing number appears only once (it’s in the range but not the array), so it survives. Everything else evaporates, and the lone survivor is your answer.

def find_missing_xor(arr, n=100):
    result = 0
    for i in range(1, n + 1):   # XOR the full range
        result ^= i
    for x in arr:               # XOR the actual values
        result ^= x
    return result               # the lone survivor

A tiny worked example

Let’s shrink it to n = 4 with 3 missing, so the array is [1, 2, 4]. In binary:

1 = 001
2 = 010
3 = 011
4 = 100

XOR of the full range 1^2^3^4:

001 ^ 010 = 011
011 ^ 011 = 000
000 ^ 100 = 100   →  4

XOR of the array 1^2^4:

001 ^ 010 = 011
011 ^ 100 = 111   →  7

Combine them: 4 ^ 7 = 100 ^ 111 = 011 = 3. ✅ The missing number is 3.

• Time: O(n).
• Space: O(1).

---

Bonus: when the array is sorted (binary search)

Everything above runs in O(n) and ignores ordering. But if the array arrives already sorted, you can do better than linear time.

The key observation: in a complete sorted array, the value at index i (0-based) would be i + 1. Index 0 holds 1, index 1 holds 2, and so on. Once a number goes missing, every element after the gap shifts left by one — so from the gap onward, arr[i] no longer equals i + 1. That gives a clean boundary to binary search for.

def find_missing_sorted(arr):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == mid + 1:
            lo = mid + 1        # everything up to mid is intact; gap is right
        else:
            hi = mid - 1        # gap is at or before mid
    return lo + 1               # first "shifted" index points at the missing value

• Time: O(log n).
• Space: O(1).

---

What if more than one number is missing?

This is where the elegant tricks start to crack, and the “boring” approach quietly wins.

• Seen array — survives effortlessly. Don’t return on the first False; collect all of them. It scales to any number of missing values with zero changes to the idea.
• Sum formula — breaks. One equation, multiple unknowns. With two missing numbers you’d need a second equation (e.g. comparing the sum of squares as well) to solve the system. Beyond two, it becomes impractical fast.
• XOR — mostly breaks. XOR’ing everything now yields the XOR of all the missing numbers combined, not each one individually. For the exact case of two missing numbers there’s a clever rescue (split the numbers into two groups based on a differing bit, then XOR each group separately), but it’s fiddly, and it doesn’t extend cleanly to three or more.
• Binary search — breaks. It assumes a single shift point in the sorted array. Multiple gaps mean multiple shift points, and the clean boundary disappears.

The lesson: the specialized math tricks are gorgeous for the exact problem they’re built for, while the humble seen array is the robust generalist.

---

Comparison at a glance

Approach	Time	Space	Works on unsorted?	Multiple missing?	Main caveat
Seen array	O(n)	O(n)	✅	✅ scales naturally	Extra O(n) memory
Sum formula	O(n)	O(1)	✅	❌ one equation	Overflow in fixed-width ints
XOR	O(n)	O(1)	✅	⚠️ special trick only for 2	Returns XOR of missings, not each
Binary search	O(log n)	O(1)	❌ needs sorted	❌ assumes one gap	Only free if input is pre-sorted

---

Your turn 🧩

Every solution above is hard-wired for the range 1 to 100. But the real world isn’t always so tidy.

Suppose the array holds numbers from some arbitrary m to n — say 50 to 150 — still unsorted, still exactly one missing. How would you adapt the sum formula and the XOR approach to handle that general range?

I won’t spoil it — the change is small and satisfying once it clicks. Have a go, and see whether your fix feels as clean as the original trick did. Drop your solution in the comments.