Skip to content

S1Q3 · Find Missing Number in a Range

📁 GitHub
⚡ 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 sum of the list to find the missing number.

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

Key rules: - Range is 1 to n inclusive - Exactly one number is missing - List may contain duplicates (as per the example) - deduplicate with set() before summing - n*(n+1)//2 is the sum of all integers from 1 to n

Problem Statement

Problem

Write a function find_missing_number(nums, n) that finds the one 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 
3

Understanding the problem

The list should contain every number from 1 to n exactly once, but one is missing and some may be duplicated. To find the missing number:

  1. Compute the expected sum of 1 to n: n*(n+1)//2
  2. Compute the actual sum of unique values in the list
  3. The difference is the missing number

Sum formula: n*(n+1)//2

The sum of all integers from 1 to n is always n*(n+1)//2. For n=6: 6*7//2 = 21. This is a classic formula worth memorising - it turns a problem that looks like it needs a loop into a single arithmetic expression.

Tracing the example

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

Expected sum (1 to 6):  6 * 7 // 2  =  21
Unique values in list:  {1, 2, 4, 5, 6}
Actual sum:             1 + 2 + 4 + 5 + 6  =  18
Missing number:         21 - 18  =  3

Why deduplicate with set()?

The example list [1, 4, 2, 4, 6, 5, 6] contains duplicates - 4 and 6 each appear twice. If you sum the raw list you get 1+4+2+4+6+5+6 = 28, which gives 21 - 28 = -7 - completely wrong.

Converting to a set first removes duplicates, giving the correct unique sum.

sum(nums)        # 28 - wrong (counts duplicates)
sum(set(nums))   # 18 - correct (unique values only)

Solution approaches

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

One line. Expected sum minus actual unique sum = missing number.

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

Same logic, each step named for clarity.

def find_missing_number(nums: list, n: int) -> int:
    full_set    = set(range(1, n + 1))   # {1, 2, 3, 4, 5, 6}
    actual_set  = set(nums)              # {1, 2, 4, 5, 6}
    missing     = full_set - actual_set  # {3}
    return missing.pop()

Compute the set of all numbers 1 to n, subtract the set of numbers present, and the remainder is the missing number. set.pop() retrieves the single element. Clean and intuitive - reads almost like plain English.

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

Check each number 1 to n against the set of seen values. Returns as soon as the missing one is found. Slightly less elegant but very easy to follow.

Key takeaways

01

n*(n+1)//2 - sum formula

The sum of integers from 1 to n. Use integer division // to keep the result an int. Appears in many "find the missing/extra number" problems.

02

Deduplicate before summing

If the list can contain duplicates, always sum(set(nums)) not sum(nums). The example in this problem has duplicates - missing this costs the full question mark.

03

Set difference for "what's missing"

set(range(1, n+1)) - set(nums) directly gives the missing elements as a set. Works even if multiple numbers were missing - more general than the sum approach.