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.