Finding the Missing Number in a Sequence

One of the classic interview problems I’ve been practicing recently is:

Find the Missing Number in a Sequence

You’re given an array containing n distinct numbers taken from 0 to n. Find the missing number.

Example

• Input: [3, 0, 1]
• Output: 2

My First Approch: Using a Set

The very first solution I wrote was with a Set. The idea is simple: put all numbers into a set for O(1) lookups, then check from 0 to n which number is missing:

Complexity:

• Time: O(n) (building the set + looping once).
• Space: O(n) (since we store all numbers in the set).

👉 This works fine, but it’s not as space-efficient as the sum formula or the XOR approach, which only use O(1) extra space.

A Common Approach: Using the Sum Formula

The common solution that usually comes to mind is to compare the expected sum of numbers 0 to n with the actual sum of the array:

This works well and is easy to explain in an interview.

Complexity:

• Time: O(n) (two passes: one to compute expected sum, one for the array sum).
• Space: O(1) (only a couple of variables).

👉 This is clear, efficient, and interview-friendly.

A Different Approach: XOR

Then I thought about a more “bitwise” solution using XOR.

The neat trick here is that XOR cancels out identical numbers:

• x ^ x = 0
• x ^ 0 = x

So if you XOR all numbers from 0 to n, and then XOR all numbers in the array, everything cancels out — except the missing number.

Complexity:

• Time: O(n) (two passes again, just XOR instead of addition).
• Space: O(1) (a single accumulator variable).

👉 This solution feels almost like a magic trick, though it may be less intuitive for those unfamiliar with bitwise operations.

Final Thought

If you were the interviewer, how would you react to the XOR solution? Would you see it as a clever use of bitwise operations, or as unnecessary complexity when the sum formula is simpler?

Sometimes the real challenge in interviews isn’t just solving the problem, but deciding how to balance creativity and clarity.