Python Program to Find Missing Number in Array

You can find the missing number in an array of size n containing numbers from 1 to n+1 by calculating the expected sum with total = (n+1)*(n+2)//2 and subtracting the actual sum of array elements with missing = total - sum(arr).

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 array should contain all numbers from 1 to n+1 but one is missing. Calculate the sum of all numbers from 1 to n+1 using the formula for the sum of an arithmetic series. Then subtract the sum of the given array from this total. The difference is the missing number.

Algorithm

1

Get the input array and find its length n.

2

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

3

Calculate the sum of all elements in the input array.

4

Subtract the array sum from the total sum to find the missing number.

5

Return or print the missing number.

Code

python

def find_missing_number(arr):
    n = len(arr)
    total = (n + 1) * (n + 2) // 2
    missing = total - sum(arr)
    return missing

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

Output

3

Dry Run

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

1

Calculate length

Length n = 5

2

Calculate total sum

total = (5 + 1) * (5 + 2) // 2 = 6 * 7 // 2 = 21

3

Calculate sum of array

sum(arr) = 1 + 2 + 4 + 5 + 6 = 18

4

Find missing number

missing = total - sum(arr) = 21 - 18 = 3

Step	Value
Length n	5
Total sum	21
Sum of array	18
Missing number	3

Why This Works

Step 1: Calculate expected sum

The formula total = (n+1)*(n+2)//2 gives the sum of all numbers from 1 to n+1, which is what the array should contain if no number was missing.

Step 2: Sum the given array

Adding all elements in the array gives the actual sum of the numbers present.

Step 3: Subtract to find missing

Subtracting the actual sum from the expected total reveals the missing number because it accounts for the gap.

Alternative Approaches

Using XOR operation

python

def find_missing_xor(arr):
    n = len(arr) + 1
    xor_all = 0
    xor_arr = 0
    for i in range(1, n + 1):
        xor_all ^= i
    for num in arr:
        xor_arr ^= num
    return xor_all ^ xor_arr

# Example usage
arr = [1, 2, 4, 5, 6]
print(find_missing_xor(arr))

This method uses bitwise XOR to find the missing number without using sum, which can be faster and avoids overflow in some languages.

Sorting and checking neighbors

python

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

# Example usage
arr = [1, 2, 4, 5, 6]
print(find_missing_sort(arr))

This method sorts the array and checks where the sequence breaks. It is less efficient due to sorting but easy to understand.

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

Time Complexity

The solution loops through the array once to sum elements, so it runs in linear time O(n).

Space Complexity

Only a few variables are used for sums and length, so space complexity is constant O(1).

Which Approach is Fastest?

The sum formula method is fastest and simplest. XOR is also O(n) but can be faster in some cases. Sorting is slower at O(n log n).

Approach	Time	Space	Best For
Sum formula	O(n)	O(1)	Simple, efficient for consecutive numbers
XOR operation	O(n)	O(1)	Avoids overflow, bitwise operations
Sorting and checking	O(n log n)	O(1)	Easy to understand, less efficient