Python Program to Find Missing Number in Array

Finding a missing number in a sequence is a very common interview and competitive programming problem.

You are usually given numbers from 1 to n with one number missing, and you need to find it.

1. Understanding the Problem

Given an array containing numbers from 1 to n with one number missing, find the missing number.

Input: [1, 2, 4, 5, 6]
Output: 3

2. Method 1: Using Sum Formula

              
Python

          Mathematical approach
        
def find_missing(arr, n):
    total = n * (n + 1) // 2
    return total - sum(arr)

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

Uses arithmetic series formula for O(n) solution.

3. Method 2: Using XOR

              
Python

          Bitwise approach
        
def find_missing_xor(arr, n):
    xor1 = 0
    xor2 = 0

    for i in range(1, n+1):
        xor1 ^= i

    for num in arr:
        xor2 ^= num

    return xor1 ^ xor2

print(find_missing_xor([1,2,4,5,6], 6))

Efficient and avoids overflow issues.

4. Method 3: Using Loop Search

              
Python

          Simple search
        
def find_missing(arr, n):
    for i in range(1, n+1):
        if i not in arr:
            return i

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

Simple but less efficient O(n²) approach.

5. Method 4: Using Sorting

              
            
Python

          Sorted check
        
def find_missing(arr):
    arr.sort()
    for i in range(len(arr)):
        if arr[i] != i + 1:
            return i + 1
    return len(arr) + 1

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

Works well when array is nearly sorted.

6. Method 5: Handling Edge Cases

              
            
Python

          Edge handling
        
arr = list(map(int, input().split()))
n = len(arr) + 1

if not arr:
    print(1)
else:
    print(n * (n + 1) // 2 - sum(arr))

Handles empty and minimal input cases.

7. Algorithm

1. Determine expected range 1 to n.

2. Compute expected sum or XOR.

3. Compare with actual array values.

4. Return missing number.

8. Common Mistakes

1. Wrong value of n.

2. Using list search in large datasets.

3. Ignoring edge cases.

4. Off-by-one errors.

9. Applications

1. Data validation.

2. Error detection.

3. Interview coding problems.

4. Sequence analysis.

Conclusion

Finding a missing number is a fundamental problem that builds strong logical and mathematical thinking in Python.

The sum formula and XOR methods are the most efficient approaches.