How do you find the missing number in 0..n? | Interview Question

Q: How do you find the missing number in 0..n?

**Target Audience:** Beginners preparing for coding interviews — you should know what an array and a loop are; nothing else is assumed. **Difficulty:** Easy **Language:** Python 3 > **How to read this doc:** Each idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every output shown in the **Verified** section was produced by actually running the Python code with `python3 main.py`; nothing is quoted from memory. ## 1. Why This Even Matters — A Story First Picture a cloakroom with tickets numbered 0 to 10. At the end of the night, eleven tickets were handed out but only ten coats come back, and the attendant wants to know which ticket number never returned. She could line the returned tickets up in order and look for the gap (that is sorting), or tick them off on a checklist (that is a hash set). But there is a cleverer trick: she knows the numbers 0 to 10 add up to 55. Add up the ten returned tick

The problem

Question presented to candidate: "You get a list of n distinct integers taken from the range 0 to n, so exactly one value in that range is missing. Write a Python function that returns it, and tell me the time and space cost."

What a strong answer should cover:

The sum formula n * (n + 1) // 2 - sum(nums) and why it works (the range is fully known in advance).
The XOR alternative and the cancelling property a ^ a == 0.
O(n) time and O(1) extra space for both, versus O(n log n) for sorting and O(n) memory for a set.
Python specifics: ints never overflow, // keeps the result an int (plain / gives a float), and sum() and enumerate() keep it short.
Edge cases: missing value is 0 or n, single element.

Clarifying questions expected:

"Are the values distinct, and is exactly one missing?" — the sum and XOR tricks depend on it.
"Is the range 0..n or 1..n, and how large can n get?" — changes the formula and whether it overflows.

Code / implementation expected: Yes — a short function in Python; the sum version is two lines.

arrays
math

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you should know what an array and a loop are; nothing else is assumed. Difficulty: Easy Language: Python 3

How to read this doc: Each idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every output shown in the Verified section was produced by actually running the Python code with python3 main.py; nothing is quoted from memory.

1. Why This Even Matters — A Story First

Picture a cloakroom with tickets numbered 0 to 10. At the end of the night, eleven tickets were handed out but only ten coats come back, and the attendant wants to know which ticket number never returned. She could line the returned tickets up in order and look for the gap (that is sorting), or tick them off on a checklist (that is a hash set). But

The solution is hidden so you can try first

11 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonSum, XOR and hash set on the standard cases

Practice

PythonWhat 32-bit overflow does to the sum formula

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.