PPractick

The problem

A ticketing system issues seat numbers 0 to n for an event of n + 1 seats, and after the doors close it has a list of the n seats that were scanned, all distinct. Exactly one seat number is missing from the list, and security wants to know which one. Sorting the list or building a lookup set would work, but there's a neat O(n)-time, O(1)-space answer: the numbers 0..n have a known total (or a known XOR), so whatever is missing from the list's total is the missing seat.

Example: [3, 0, 1] (n = 3, range 0..3) → 2.

Function signature

int missingNumber(const vector<int>& nums);  // nums has n distinct values from [0, n]

Test cases

Input nums	Output	Explanation
[3, 0, 1]	2	Range 0..3
[0, 1]	2	The missing number can be n itself
[9, 6, 4, 2, 3, 5, 7, 0, 1]	8
[0]	1
[1]	0	The missing number can be 0

(Confirm: all values are distinct and lie in [0, n], where n is the array's length; exactly one number is missing.)

How interviewers phrase it

• "Given n distinct numbers from 0 to n, find the missing one" (LeetCode 268).
• The 1..N version: "An array of size N − 1 contains 1..N with one missing."
• Follow-ups combine it with a repeated number: "find the missing and repeating number" (S.No 98).

Clarifying questions to ask

1. Is the range 0..n or 1..n?
2. Are the values guaranteed distinct, with exactly one missing?
3. Can I modify the array?
4. How large is n? (Sum overflow.)

Follow-ups to expect

1. "Why does the sum formula work?"
2. "Can the sum overflow?"
3. "How does the XOR version work?"
4. "Other approaches?"
5. "Complexity?"

Related questions

• Kth Missing Positive Number Easy
• Find the number that appears once, and other numbers twice Medium
• Find the repeating and missing number Medium
• Divide two numbers without multiplication and division Medium
• Single Number - I Medium
• XOR of numbers in a given range Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in