Find the Missing Number in 1 to N in Python

That is exactly what the missing number in 1 to N in Python is about. You are given a list of numbers that should span from 1 to N — but one number is absent. Your job is to find it efficiently.

This problem shows up in almost every coding interview. Companies like Amazon, TCS, Infosys, and Wipro love it because it tests your understanding of arrays, mathematics, and bit manipulation — all in one small problem.

The brute-force solution works, but a 10-line nested loop will not impress an interviewer. Knowing the sum formula method and the XOR method will — and both are simple once you see the pattern.

02: Problem Statement

Examples

Input : n = 5,  array = [1, 2, 4, 5]
Output: 3

# 3 is missing from 1..5

Input : n = 5,  array = [2, 3, 1, 5]
Output: 4

# 4 is missing from 1..5

Input / Output Format

• First line: integer n
• Second line: n−1 space-separated integers
• Output: print the missing integer

Constraints

• 2 ≤ n ≤ 10⁶
• All elements are distinct
• Exactly one number is missing
• 1 ≤ array[i] ≤ n

03: Why This Problem Matters

You might wonder — why do interviewers ask such a simple-looking question? Because the real test is not whether you can find the answer. It is how you find it.

• It checks if you know your math (sum formula)
• It checks if you know bitwise operations (XOR)
• It is a foundation problem for harder ones like “find two missing numbers” or “find the duplicate”
• It trains you to think about time and space trade-offs early

Master this problem and the harder variants become significantly easier.

04: Naive Approach — O(n²)

The most obvious way: loop from 1 to N and for each number, scan the entire array to check if it exists.

deffind_missing_naive(arr, n):
    for num in range(1, n + 1):
        if num not in arr:   # 'in' scans the whole list each time
            return num

n   = int(input())
arr = list(map(int, input().split()))
print(find_missing_naive(arr, n))

For n = 5 and array [1, 2, 4, 5]:

1. Check if 1 is in array → yes
2. Check if 2 is in array → yes
3. Check if 3 is in array → no → return 3

It works, but for large inputs this is painfully slow. Time complexity is O(n²) because the inner in operator scans the full list each iteration.

05: Optimal Approach 1 — Sum Formula O(n)

Here is a neat mathematical trick to find the Missing Number in 1 to N in Python. The sum of all integers from 1 to N has a closed-form formula:

Why does this work? The expected sum counts every number from 1 to N exactly once. The actual array is missing exactly one number. Subtracting the two sums isolates that missing value perfectly.

def find_missing_sum(arr, n):
    expected = n * (n + 1) // 2   # total sum if nothing was missing
    actual   = sum(arr)           # sum of what we actually have
    return expected - actual       # difference = missing number

n   = int(input())
arr = list(map(int, input().split()))
print(find_missing_sum(arr, n))

06: Optimal Approach 2 — XOR Method O(n)

XOR is a bitwise operation with one beautiful property: a XOR a = 0 and a XOR 0 = a. Any number XOR’d with itself cancels out.

So if you XOR all numbers from 1 to N, and then XOR that result with all elements of the array, every number that appears in both will cancel. Only the missing number — which appeared in 1..N but not in the array — will be left.

deffind_missing_xor(arr, n):
    xor_full  = 0
    xor_array = 0

    for i in range(1, n + 1):
        xor_full ^= i      # XOR of 1 to n

    for num in arr:
        xor_array ^= num   # XOR of array elements

    return xor_full ^ xor_array  # leftover = missing number

n   = int(input())
arr = list(map(int, input().split()))
print(find_missing_xor(arr, n))

07: Flowchart 

08: Pseudocode

BEGIN
  READ n
  READ array of (n-1) integers

  // Sum Method
  expected ← n * (n + 1) / 2
  actual   ← SUM(array)
  PRINT expected - actual

  // XOR Method
  xor_full  ← XOR of all integers 1..n
  xor_array ← XOR of all elements in array
  PRINT xor_full XOR xor_array
END

09: Dry Run — Step by Step

Let’s trace through [1, 2, 4, 5] with n = 5 using the sum method.

Now with XOR on the same input:

10: Line-by-Line Explanation

Sum Method

• n * (n+1) // 2 → Gauss formula for sum of 1 to n; // ensures integer result
• sum(arr) → Python’s built-in that adds all elements in one pass
• expected - actual → the gap is exactly the missing number

XOR Method

• First loop XORs 1, 2, 3, …, n together
• Second loop XORs every element in the array
• Final XOR: paired numbers cancel (a^a=0), leaving only the missing one

11: Complexity Analysis

Both optimal methods use constant space — no auxiliary array, no hash map. The XOR method has a slight edge because it avoids integer overflow for extremely large values of n.

12: Test Cases

13: Edge Cases

• n = 1, array = []: Expected sum = 1, actual = 0 → missing = 1
• Empty array: Treat as n=1 with missing = 1. Always validate input first.
• Duplicates in array: The problem guarantees distinct values. If duplicates exist, both sum and XOR methods break — handle separately.

14: Common Interview Questions

Q1 — Why does XOR work for this problem?

Because XOR of a number with itself is always 0, and XOR with 0 keeps the number unchanged. When you XOR the full range 1..N with the array, every number that appears in both cancels out. Only the missing number — present in 1..N but absent from the array — survives.

Q2 — Which method is better: sum or XOR?

Both are O(n) time and O(1) space. The sum formula is easier to read and explain. The XOR method is safer for huge values of n where n*(n+1)/2 might overflow a 32-bit integer (in languages like C/Java). In Python, integers have unlimited precision, so overflow is not a concern — but XOR is still a good habit.

Q3 — Can these methods handle duplicate values?

No. The sum formula and XOR method both assume every number from 1 to N appears at most once. If there are duplicates, neither method gives the correct answer. You would need a sorting-based or hash-set approach for that variant.

Q4 — Which companies ask this problem?

Amazon, Infosys, TCS, Wipro, Accenture, Capgemini, and many product startups include this in their screening rounds. It also appears frequently in competitive programming warm-up sets.

Q5 — What if two numbers are missing?

This is a follow-up problem. You can extend the XOR trick or use two equations from sum and sum-of-squares to solve it in O(n) time. That’s a topic for another post!

15: Real-World Applications

• Data validation: Checking if all invoice IDs in a sequence are present
• Ticket systems: Finding skipped ticket numbers in a booking system
• Inventory tracking: Detecting a missing product ID from a scanned list
• Database integrity: Verifying auto-increment primary keys have no gaps

16: Mistakes Beginners Often Make

• Using n*(n+1)/2 with / (float division) instead of // in Python → can cause type mismatch
• Confusing n (the full range) with len(arr) (which is n−1)
• Forgetting to read n from input separately — computing it as len(arr)+1 works but is less general
• Assuming the array is always sorted — neither method requires sorting

Conclusion

The missing number problem is one of those problems where the naive solution is obvious, but the elegant solution is what gets remembered. Once you internalize the sum formula trick — expected minus actual — and the XOR cancellation trick, you have two powerful tools that show up in many harder problems down the road.

Both methods run in linear time and use constant space. Practice writing them from memory, understand the intuition behind each, and you will be well-prepared when this comes up in your next interview.

FAQ