DocsHub
PythonIntermediate

Find Missing Number

Learn how to find the missing number in a sequence from 1 to N in Python.

Find Missing Number

Problem

Given a list containing n-1 numbers from 1 to n with exactly one number missing, find the missing number.

Input:  [1, 2, 4, 5, 6]   (n=6)
Output: 3

Input:  [2, 3, 4, 5, 6]   (n=6)
Output: 1

Input:  [1, 2, 3, 4, 5]   (n=6)
Output: 6

Input:  [1]               (n=2)
Output: 2

Logic

The key insight:

If no number was missing, the sum of 1 to n is always:

sum = n × (n + 1) / 2

Example: sum of 1 to 6 = 6 × 7 / 2 = 21

So if the actual sum of the list is 18, the missing number is 21 - 18 = 3.

Flow

Start n = length of list + 1because one number is missing expected = n × n+1 / 2sum of 1 to n actual = sum of all numbers in list missing = expected - actual Return missing

Solution 1 — sum formula

The fastest and cleanest approach. Calculate the expected sum and subtract the actual sum.

def find_missing(numbers):
    # n is the length + 1 because one number is missing
    n = len(numbers) + 1

    # expected sum of 1 to n using Gauss formula
    expected_sum = n * (n + 1) // 2

    # actual sum of the given list
    actual_sum = sum(numbers)

    # the difference is the missing number
    return expected_sum - actual_sum


print(find_missing([1, 2, 4, 5, 6]))   # 3
print(find_missing([2, 3, 4, 5, 6]))   # 1
print(find_missing([1, 2, 3, 4, 5]))   # 6
print(find_missing([1]))               # 2

Code Execution — Solution 1

Trace through find_missing([1, 2, 4, 5, 6]):

StepCodeResult
nlen([1,2,4,5,6]) + 16
Expected sum6 × 7 // 221
Actual sum1+2+4+5+618
Missing21 - 183

Trace through find_missing([2, 3, 4, 5, 6]):

StepCodeResult
nlen([2,3,4,5,6]) + 16
Expected sum6 × 7 // 221
Actual sum2+3+4+5+620
Missing21 - 201

Trace through find_missing([1, 2, 3, 4, 5]):

StepCodeResult
nlen([1,2,3,4,5]) + 16
Expected sum6 × 7 // 221
Actual sum1+2+3+4+515
Missing21 - 156

n × (n + 1) / 2 is called the Gauss formula — named after mathematician Carl Friedrich Gauss. The story goes that as a child, Gauss quickly summed 1 to 100 by pairing numbers: (1+100) + (2+99) + ... = 50 pairs × 101 = 5050. The formula captures this pattern for any n.

Solution 2 — using a loop

Manually calculate both sums by looping. More explicit — shows the steps clearly.

def find_missing(numbers):
    n = len(numbers) + 1

    # calculate expected sum manually
    expected_sum = 0
    for i in range(1, n + 1):
        expected_sum += i

    # calculate actual sum manually
    actual_sum = 0
    for num in numbers:
        actual_sum += num

    return expected_sum - actual_sum


print(find_missing([1, 2, 4, 5, 6]))   # 3
print(find_missing([2, 3, 4, 5, 6]))   # 1
print(find_missing([1, 2, 3, 4, 5]))   # 6

Code Execution — Solution 2

Trace through find_missing([1, 2, 4, 5, 6]):

Expected sum loop — range(1, 7) = 1, 2, 3, 4, 5, 6:

iexpected_sum
11
23
36
410
515
621

Actual sum loop — [1, 2, 4, 5, 6]:

numactual_sum
11
23
47
512
618

Missing = 21 - 18 = 3

Solution 3 — using XOR

XOR is a bitwise operation with a special property — a XOR a = 0 and a XOR 0 = a. If you XOR a number with itself, they cancel out. XOR all numbers from 1 to n with all numbers in the list — only the missing number will not cancel.

def find_missing(numbers):
    n = len(numbers) + 1

    # XOR all numbers from 1 to n
    xor_all = 0
    for i in range(1, n + 1):
        xor_all ^= i   # ^= is XOR assignment

    # XOR all numbers in the list
    xor_list = 0
    for num in numbers:
        xor_list ^= num

    # missing number — everything else cancelled out
    return xor_all ^ xor_list


print(find_missing([1, 2, 4, 5, 6]))   # 3
print(find_missing([2, 3, 4, 5, 6]))   # 1
print(find_missing([1, 2, 3, 4, 5]))   # 6

Code Execution — Solution 3

Trace through find_missing([1, 2, 4, 5, 6]):

XOR all numbers 1 to 6: xor_all = 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6

XOR all numbers in list: xor_list = 1 ^ 2 ^ 4 ^ 5 ^ 6

Final XOR: xor_all ^ xor_list = (1^1) ^ (2^2) ^ 3 ^ (4^4) ^ (5^5) ^ (6^6) = 0 ^ 0 ^ 3 ^ 0 ^ 0 ^ 0 = 3

Every number that appears in both cancels to 0. Only 3 — the missing number — remains.

XOR properties:

  • a ^ a = 0 — same number cancels itself
  • a ^ 0 = a — XOR with 0 changes nothing
  • XOR is commutative and associative — order does not matter

These properties make XOR perfect for finding a missing or duplicate element.

Solution 4 — using a set

Put all numbers in a set, then check which number from 1 to n is not in the set.

def find_missing(numbers):
    n = len(numbers) + 1

    # convert list to set for O(1) lookup
    number_set = set(numbers)

    # check each number from 1 to n
    for i in range(1, n + 1):
        if i not in number_set:
            return i

    return None   # no missing number found


print(find_missing([1, 2, 4, 5, 6]))   # 3
print(find_missing([2, 3, 4, 5, 6]))   # 1
print(find_missing([1, 2, 3, 4, 5]))   # 6

Code Execution — Solution 4

Trace through find_missing([1, 2, 4, 5, 6]):

number_set = {1, 2, 4, 5, 6}

ii in number_set?
1Yes
2Yes
3No → return 3

Stops as soon as it finds the missing number.

Solution 5 — sorting

Sort the list then check where the sequence breaks.

def find_missing(numbers):
    numbers = sorted(numbers)   # sort in place copy

    # check each consecutive pair
    for i in range(len(numbers) - 1):
        # if next number is not current + 1 — gap found
        if numbers[i + 1] != numbers[i] + 1:
            return numbers[i] + 1

    # if no gap found inside — missing number is at one of the ends
    # check if 1 is missing
    if numbers[0] != 1:
        return 1

    # missing number must be at the end
    return numbers[-1] + 1


print(find_missing([1, 2, 4, 5, 6]))   # 3
print(find_missing([2, 3, 4, 5, 6]))   # 1
print(find_missing([1, 2, 3, 4, 5]))   # 6

Code Execution — Solution 5

Trace through find_missing([4, 1, 5, 2, 6]):

After sorting: [1, 2, 4, 5, 6]

inumbers[i]numbers[i+1]Gap?
012No
124Yes → return 2 + 1 = 3

Trace through find_missing([2, 3, 4, 5, 6]):

After sorting: [2, 3, 4, 5, 6]

No gap inside the sequence → check numbers[0] = 2 ≠ 1 → return 1

Performance comparison

SolutionTime complexitySpace complexityNotes
Solution 1 — sum formulaO(n)O(1)Best overall
Solution 2 — manual loopO(n)O(1)Same as 1, more verbose
Solution 3 — XORO(n)O(1)No overflow risk
Solution 4 — setO(n)O(n)Extra memory for the set
Solution 5 — sortingO(n log n)O(1)Slowest — sorting costs

Solution 1 (sum formula) has one potential issue — for very large n, the expected sum could overflow in languages like C or Java. Python handles arbitrarily large integers natively so this is not a problem here. But in interviews, Solution 3 (XOR) is often preferred since it has zero overflow risk in any language.

Which solution to use?

SolutionHowBest when
Solution 1Sum formulaPython — cleanest and fastest
Solution 2Manual sum loopLearning — shows the math clearly
Solution 3XORInterviews — no overflow, very clever
Solution 4Set lookupWhen you want explicit membership check
Solution 5Sort then scanWhen you need to visualize the gap

Output

3
1
6
2

Rotate Array

Learn how to rotate a list left or right by K positions in Python.

Two Sum

Learn how to find two numbers in a list that add up to a target value in Python.

On this page

Find Missing NumberProblemLogicFlowSolution 1 — sum formulaCode Execution — Solution 1Solution 2 — using a loopCode Execution — Solution 2Solution 3 — using XORCode Execution — Solution 3Solution 4 — using a setCode Execution — Solution 4Solution 5 — sortingCode Execution — Solution 5Performance comparisonWhich solution to use?Output