Find Missing Number in Python Sequence 1 to N
Find the missing number from a list containing numbers 1 to N using the arithmetic sum formula.
Python code
11 linesdef find_missing_number(nums, n):
expected_sum = n * (n + 1) // 2
actual_sum = sum(nums)
return expected_sum - actual_sum
if __name__ == "__main__":
n = 10
numbers = [1, 2, 3, 4, 5, 6, 7, 9, 10]
missing = find_missing_number(numbers, n)
print(f"The missing number is: {missing}")Output
The missing number is: 8How it works
The code computes the expected sum of all integers from 1 to n using the formula n*(n+1)//2, then subtracts the actual sum of the provided numbers. The difference equals the missing number because the formula sums the complete range while the list is missing exactly one element. This works in O(n) time and O(1) extra space, making it efficient for large n. The integer division // ensures the result is an integer even if n is odd.
Common mistakes
- Off-by-one errors when computing the expected sum, using n*(n-1)//2 instead
- Assuming the list is sorted or starts from 0 instead of 1
- Forgetting that the function expects n and the list may be shorter by exactly one element
Variations
- Use XOR operation: xor all numbers from 1 to n and all elements in list, the result is the missing number
- Sort the list and scan for the gap if the list is unsorted and you need the missing element without arithmetic
Real-world use cases
- Validating a batch of sequential IDs in a database to detect a skipped record.
- Checking that a series of event sequence numbers in a log file has no gaps.
- Verifying that a complete set of items (e.g., puzzle pieces or tickets) is present with one missing.
Sponsored
More from Algorithms & data structures
- Binary Search for Ship Capacity in Python medium
- Binary Search on Answer in Python: Koko Eating Bananas medium
- Bucket Numbers into Histogram Bin Counts in Python easy
- Container With Most Water: Two-Pointer Solution in Python medium
- Count Smaller Elements to the Right in Python easy
- Depth First Search Traversal Order in Python easy
Keep learning
Related tutorials and quizzes for this topic.