Python Program to Find Missing Number in List

You can find the missing number in a list of numbers from 1 to n by calculating expected_sum = n*(n+1)//2 and subtracting the sum of the list, like missing = expected_sum - sum(nums).

Examples

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

Output3

Input[2, 3, 1, 5]

Output4

Input[1]

Output2

How to Think About It

To find the missing number, first understand that the list should contain all numbers from 1 to n except one. 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 all numbers in the given list.

4

Subtract the list sum from the expected sum to find the missing number.

5

Return the missing number.

Code

python

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

# 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 the list should have if no number was missing.

Step 2: Sum the given list

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

Step 3: Subtract to find missing

The difference between expected and actual sums is the missing number because it was not added in the list.

Alternative Approaches

Using set difference

python

def find_missing_number_set(nums):
    n = len(nums) + 1
    full_set = set(range(1, n + 1))
    nums_set = set(nums)
    missing = full_set - nums_set
    return missing.pop()

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

Using XOR operation

python

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

XOR method is efficient and uses constant space but is 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

Only a few variables are used, 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 space and is slower.

Approach	Time	Space	Best For
Sum formula	O(n)	O(1)	Simplicity and speed
Set difference	O(n)	O(n)	Readability, small lists
XOR operation	O(n)	O(1)	Efficiency with bitwise operations