S1Q3 · Find Missing Number in a Range¶

⚡ Quick Reference

Function: find_missing_number(nums: list, n: int) -> int

Core idea: the sum of 1 to n is n*(n+1)//2. Subtract the actual sum of the list to get the missing number.

def find_missing_number(nums: list, n: int) -> int:
    return n * (n + 1) // 2 - sum(nums)

Key rules: - Expected sum of 1..n = n*(n+1)//2 - Missing number = expected sum − actual sum - O(n) time, O(1) space - no sorting or set needed

Problem Statement¶

Problem

Write a function find_missing_number(nums, n) that finds the single missing number from a list that should contain all integers from 1 to n.

Example:

Input

nums=[1, 4, 2, 4, 6, 5, 6], n=6

Output

Understanding the approach¶

The sum of all integers from 1 to n is given by the formula:

expected = n * (n + 1) / 2

For n = 6: expected = 6 × 7 / 2 = 21

Actual sum of [1, 4, 2, 4, 6, 5, 6] = 28... wait, that's larger than expected.

The list has duplicates (4 and 6 appear twice) - one duplicate takes the place of the missing number 3. So:

expected = 21
actual   = sum([1, 4, 2, 4, 6, 5, 6]) = 28

missing = expected - (actual - duplicate)

But actually the formula still works directly:

expected = n*(n+1)//2 = 21
actual   = sum(nums)  = 28

missing = 21 - 28 = -7  ← that's wrong

Hmm - let me re-read. The list has n numbers (one missing, one duplicate). So:

sum(correct list) = 1+2+3+4+5+6 = 21
sum(given list)   = 1+4+2+4+6+5+6 = 28

actual - expected = 28 - 21 = 7. The duplicate value minus the missing value = 7. But we need: missing = duplicate - 7... this doesn't resolve without knowing the duplicate.

This example has a duplicate - use set approach

The example [1, 4, 2, 4, 6, 5, 6] has duplicates (4 and 6). The sum formula only works when there is exactly one missing and no duplicates. The set approach works for both cases:

def find_missing_number(nums: list, n: int) -> int:
    return (set(range(1, n + 1)) - set(nums)).pop()

set(range(1, n+1)) is the full expected set; subtracting set(nums) leaves only the missing number.

Tracing the example¶

nums = [1, 4, 2, 4, 6, 5, 6], n = 6

Expected set: {1, 2, 3, 4, 5, 6}
Actual set:   {1, 2, 4, 5, 6}      (sets deduplicate automatically)
Difference:   {3}
Missing:      3 ✓

Solution approaches¶

Pythonic (set difference)Sum formula (no duplicates case)Explanatory (manual loop)Using lambda + filter

def find_missing_number(nums: list, n: int) -> int:
    return (set(range(1, n + 1)) - set(nums)).pop()

Works correctly even when nums contains duplicates. The set difference gives exactly the missing element.

def find_missing_number(nums: list, n: int) -> int:
    expected = n * (n + 1) // 2
    return expected - sum(nums)

Works when the list has exactly one missing element and no duplicates. O(1) extra space.

def find_missing_number(nums: list, n: int) -> int:
    num_set = set(nums)
    for i in range(1, n + 1):
        if i not in num_set:
            return i

Iterate from 1 to n and return the first number not in the list. Clear and readable.

def find_missing_number(nums: list, n: int) -> int:
    return next(filter(lambda x: x not in nums, range(1, n + 1)))

filter lazily checks each number in 1..n and returns the first one not in nums.

Key takeaways¶

01

Set difference handles duplicates safely

set(range(1, n+1)) - set(nums) works regardless of duplicates in nums because sets automatically deduplicate. The result is always the single missing number.

02

Sum formula - fast but assumes no duplicates

n*(n+1)//2 - sum(nums) is O(n) time and O(1) space. It only works correctly when the list has exactly one missing number and no duplicate values.

03

set.pop() retrieves the single element

After the set difference, only one element remains. .pop() removes and returns it. Since there's guaranteed to be exactly one missing number, this is safe.