Python Program to find missing number in array

In this tutorial, you will learn writing a program using Python to find the missing number in integer array of 1 to 100. 

This Program is not generic, It has some limitations like 

• It can find only one missing number in an array.
• Here we are just adding numbers from 0 to n, where n is number of elements array can have.
•  User can give input only between 0 to n.
• To find missing number, subtract sum of numbers given by user from total sum of numbers from 0 to n.

Also Read This:  Java Program to find missing number in array. 

Python Program to find missing number in Array

Program 1: Using the Formula for the Sum

The sum of the first n natural numbers is given by the formula 𝑛×(𝑛+1)/2​. If one number is missing, the sum of the array will be less than this total by exactly the missing number.

# Initialize the array
arr = [1, 2, 3, 5]

# Calculate the total number of elements expected (including the missing one)
n = len(arr) + 1

# Calculate the sum of the first n natural numbers
total_sum = (n * (n + 1)) // 2  # Use integer division for safety

# Calculate the sum of the elements in the array
sumArr = sum(arr)

# Calculate the missing number
missing_number = total_sum - sumArr

# Print the missing number
print("Missing number =", missing_number)

Output

Missing number = 4

Explanation

This method calculates the expected sum of the first n natural numbers and subtracts the sum of the array from this expected sum. The result is the missing number.

Program 2: Using Sorting

By sorting the array, you can simply iterate through and identify where the numbers skip.

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

array = [1, 2, 3, 4]
print("Missing number =", get_missing_number(array))  

Output

Missing number = 5

Explanation

After sorting the array, the program checks each element. If any element doesn’t match its index + 1 (since array indices start at 0), it means that the current index + 1 is the missing number. If the loop completes, the missing number is n+1.

Program 3: Using Set for Direct Lookup

This method involves creating a set from the array, then checking which number from 1 to n is not in the set.

array = [1, 2, 3, 4]

num_set = set(array)

n = len(array) + 1

missing_number = None

for number in range(1, n + 1):
    if number not in num_set:
        missing_number = number
        break  

if missing_number is not None:
    print("Missing number =", missing_number)
else:
    print("No missing number, the sequence is complete.")

Output

Missing number = 5

Explanation:

This method checks each number from 1 to n against a set of numbers in the array. The first number not found in the set is the missing number.