L2 · Working engineerLists & arrays~6 min · 5 tests#4

Find the Missing Number from 1 to N

Find the one missing number in a list of 1..N using the sum formula or XOR — O(n) time, O(1) space. Run tests and compare approaches in Python.

The problem

nums holds the numbers 1..N with exactly one missing (so len(nums) == N - 1). The list may be in any order. Return the missing number.

Examples

Example 1
Input
```
missing_number([1, 2, 3, 5, 6])
```
Expected output
```
4
```
Example 2
Input
```
missing_number([2, 3, 1, 5])
```
Expected output
```
4
```

+ 3 hidden tests on Submit — N = 2, 1 missing, N = 2, 2 missing, last missing.

Edge cases to ask about

Missing first value (1)
Missing last value (N)
Unsorted input

Hints

0/3

How an interviewer scores this

0/9

1. Understand the problemRestate it, ask about edge cases and input size.
2. Write a brute-force solutionCorrect first, clever later.
3. Get the correct outputautoAll visible examples pass.
4. Analyse time complexityautoCommit to a Big-O in the Complexity Lab.
5. Analyse space complexityautoExtra memory, not the input.
6. Identify the bottleneckautoMeasure your code — where does it bend?
7. OptimiseUsually: a set or dict instead of a scan.
8. Explain why it worksSay it out loud to Solvi.
9. Test the edge casesautoSubmit passes every hidden test.

Python 3.13 · missing_number

def missing_number(nums):
    """nums is 1..N with one value missing. Return it."""
    # Write your solution here
    pass

⌘/Ctrl + Enter runs the examples

Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.

Complexity Lab

What does this cost as n grows?

Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.

Time complexity of the optimal solution

Space complexity (extra memory)

Pick both to reveal the answer.

Measure it

Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.

From brute force to optimal

The progression an interviewer wants to hear, one step at a time.

Approach	Time	Space	Idea
Check each 1..N with `in`	O(n²)	O(1)	n membership tests, each scanning the list.
Set difference	O(n)	O(n)	set(range(1, n+1)) - set(nums).
Gauss sum formula	O(n)	O(1)	Expected total n(n+1)/2 minus the actual total is the missing value.
bestXOR trick	O(n)	O(1)	XOR all of 1..N with all of nums; pairs cancel and the missing value remains. No overflow risk in other languages.

Walkthrough of the optimal approach (try it yourself first)

The numbers 1..N add up to N(N+1)/2. Subtract the actual sum and what is left is the missing number.

In Python integers never overflow, so the formula is safe. In Java or C++ the XOR version is the one interviewers like, because it never builds a big intermediate total.

Complexity: O(n) time, O(1) space. sum() touches each element once; the formula is constant work. No extra structure grows with n.

Reveal the reference solution

def missing_number(nums):
    n = len(nums) + 1
    return n * (n + 1) // 2 - sum(nums)

The brute force, for comparison

def missing_number(nums):
    for i in range(1, len(nums) + 2):
        if i not in nums:        # list scan each time
            return i

Follow-ups interviewers ask

Two numbers are missing — how do you find both?
The list is a stream you can read only once.

Frequently asked interview questions

Core interview concepts, complexities, and follow-ups scored by hiring teams.

What is the time complexity of Find the Missing Number from 1 to N in Python?

The optimal solution runs in O(n) time and O(1) auxiliary space. sum() touches each element once; the formula is constant work. No extra structure grows with n.

What is the brute-force approach, and how do you optimise it?

Check each 1..N with `in`: O(n²) time, O(1) space. n membership tests, each scanning the list. Set difference: O(n) time, O(n) space. set(range(1, n+1)) - set(nums). Gauss sum formula: O(n) time, O(1) space. Expected total n(n+1)/2 minus the actual total is the missing value. XOR trick: O(n) time, O(1) space. XOR all of 1..N with all of nums; pairs cancel and the missing value remains. No overflow risk in other languages.

What follow-up questions do interviewers ask about Find the Missing Number from 1 to N?

Two numbers are missing — how do you find both? The list is a stream you can read only once.