Python Program to Find Missing Number in a List

You can find the missing number in a list of numbers from 1 to n using the formula missing = n*(n+1)//2 - sum(numbers), where numbers is your list and n is the expected count.

Examples

Input[1, 2, 4, 5, 6]

Output3

Input[2, 3, 1, 5]

Output4

Input[1]

OutputNo missing number or 0

How to Think About It

To find the missing number, first understand that the numbers should be from 1 to n without gaps. Calculate the total sum of numbers from 1 to n using the formula n*(n+1)//2. Then subtract the sum of the given list from this total. The difference is the missing number.

Algorithm

1

Get the list of numbers and find its length n.

2

Calculate the expected sum of numbers from 1 to n+1 using the formula n*(n+1)//2.

3

Calculate the sum of the given numbers.

4

Subtract the sum of given numbers from the expected sum.

5

Return the result as the missing number.

Code

python

def find_missing_number(numbers):
    n = len(numbers) + 1
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(numbers)
    missing = expected_sum - actual_sum
    return missing

# Example usage
numbers = [1, 2, 4, 5, 6]
print(find_missing_number(numbers))

Output

3

Dry Run

Let's trace the example list [1, 2, 4, 5, 6] through the code

1

Calculate n

Length of list is 5, so n = 5 + 1 = 6

2

Calculate expected sum

expected_sum = 6 * (6 + 1) // 2 = 6 * 7 // 2 = 21

3

Calculate actual sum

actual_sum = 1 + 2 + 4 + 5 + 6 = 18

4

Find missing number

missing = expected_sum - actual_sum = 21 - 18 = 3

Step	Value
n	6
expected_sum	21
actual_sum	18
missing	3

Why This Works

Step 1: Calculate expected sum

The formula n*(n+1)//2 gives the sum of all numbers from 1 to n, which is what we expect if no number is missing.

Step 2: Sum given numbers

Adding all numbers in the list gives the actual sum present.

Step 3: Subtract to find missing

The difference between expected and actual sums is the missing number.

Alternative Approaches

Using set difference

python

def find_missing_number(numbers):
    n = len(numbers) + 1
    full_set = set(range(1, n + 1))
    missing = full_set - set(numbers)
    return missing.pop() if missing else 0

numbers = [1, 2, 4, 5, 6]
print(find_missing_number(numbers))

This method uses sets to find the missing number but uses more memory and is slower for large lists.

Using XOR operation

python

def find_missing_number(numbers):
    n = len(numbers) + 1
    xor_all = 0
    xor_list = 0
    for i in range(1, n + 1):
        xor_all ^= i
    for num in numbers:
        xor_list ^= num
    return xor_all ^ xor_list

numbers = [1, 2, 4, 5, 6]
print(find_missing_number(numbers))

XOR method is efficient and uses constant space but may be less intuitive for beginners.

Complexity: O(n) time, O(1) space

Time Complexity

The program sums the list once, which takes O(n) time where n is the number of elements.

Space Complexity

It uses only a few variables, so space complexity is O(1), constant space.

Which Approach is Fastest?

The sum formula method is fastest and simplest. The XOR method is also O(n) but less readable. The set method uses extra memory and is slower.

Approach	Time	Space	Best For
Sum formula	O(n)	O(1)	Simple and fast for any size
Set difference	O(n)	O(n)	Easy to understand but uses more memory
XOR operation	O(n)	O(1)	Efficient and memory friendly but less intuitive