Python Program to Find the Missing Number in an array/list

Our website provided core java programs examples with output aid beginners and expert coders to test their knowledge gap and learn accordingly.

Lists in Python:

Python contains a collection of built-in data types that make typical data-wrangling tasks simple. The list is one of them, a simple but useful collection type. A Python list allows you to collect Python objects in a one-dimensional row that may be accessed by position, added, removed, sorted, and subdivided.

Find the missing number in an array/list of n-1 different numbers in the range of 1 to n in linear time in Python.

Examples:

Example1:

Input:

given list= [ 1 ,3 ,2 , 6 , 5 ]

Output:

The missing number in the given list 4

Example2:

Input:

given list= [ 1 , 9 , 2 ,3 , 5 , 4 , 6 , 7 ]

Output:

The missing number in the given list 8

Program to Find the Missing Number in an array/list in Python

There are several to find the missing number in an array/list in python but to do the same thing in linear time we use either mathematical formula or bit manipulation techniques like below.

Using mathematical formula
Using XOR (bitwise operator )

Drive into Python Programming Examples and explore more instances related to python concepts so that you can become proficient in generating programs in Python Programming Language.

Method #1:Using mathematical formula

Approach:

The array’s length is n-1. So, using the formula n*(n+1)/2, the sum of all n elements, i.e. the sum of numbers from 1 to n, can be determined.

The aim is to use the above formula to find the sum of integers between 1 and n+1, where is the size of the array. Calculate the real sum of the integers in the array as well. The difference between the two is now the missing number.

Algorithm:

Calculate the length of the array and take a variable to store it say n.
Sum the first n natural numbers as totalSum= n*(n+1)/2
To hold the sum of array elements, create a variable arraySum.
Traverse the array from beginning to end.
Sum should be updated as= arraySum+ array[i].
Print the missing number as totalSum– arraySum

Below is the implementation:

def findMissingNumb(given_list):

    # calculating the length of the given list
    n = len(given_list)

    # Because a number is missing from the list, the real size is n+1.
    length = n + 1

    # Getting sum of all numbers from 1 to length using mathematical formula
    totalSum = length * (length + 1) / 2
    # calculating the sum of all elements in the given list
    # initializing a variable to store arraysum as 0
    arraysum = 0
    # Traversing the list
    for ele in given_list:
        arraysum = arraysum+ele

    # The difference between the totalsum and arraysum
    # of the integers in the list is the missing number.
    # missing number
    missnum = totalSum-arraysum
    # reeturn the missing number
    return int(missnum)


# Driver code
# given list
given_list = [1, 3, 2, 6, 5]
# passing the given list to findMissingNumb  to print the missing number

print("The missing number in the given list", findMissingNumb(given_list))

Output:

The missing number in the given list 4

Complexity Analysis of the above program:

Time Complexity: O(n)

Because only one traversal / one loop is needed

Space Complexity: O(1)

Because no extra space is needed

Method #2 : Using XOR (bitwise operator )

To overcome the problem, this method use the XOR technique.

Approach:
Certain properties are possessed by XOR like
Assume a1 ^ a2^a3… a^n = a and a1 ^a2^ a3… ^an-1 = b.
Consequently, a ^b = an

We know XOR cancels each other in equal numbers. This is something we can benefit from in the small range array for the missing number.
The aim is to calculate XOR for all items of the array and calculate XOR for all items from 1 through n+1. It is now the XOR between the two that is missing.

Algorithm:

Make two variables with the values a = 0 and b = 0.
Begin a loop from 1 to n, using i as the counter.
For each index, change a to a = a^ i.
Now iterate through the array from beginning to end.
Update b as b = b ^list[i] for each index.
The missing number should be printed as a^b.

Below is the implementation:

def findMissingNumb(given_list):
    # calculating the length of the given list
    n = len(given_list)
    # Calculating xor of all elements in the given list
    totalXor = 0
    # Traverse the given list
    for i in given_list:
        totalXor = totalXor ^ i
    # calculating xor of all elements from 1 to n+1
    # Compute XOR of all the elements from 1 to `n+1`
    for i in range(1, n + 2):
        totalXor = totalXor ^ i
    # initialize the missnum with the totalXor
    missNum = totalXor
    # return the missing number
    return missNum


# Driver code
# given list
given_list = [1, 3, 2, 6, 5]
# passing the given list to findMissingNumb  to print the missing number

print("The missing number in the given list", findMissingNumb(given_list))

Output:

The missing number in the given list 4

Complexity Analysis of the above program:

Time Complexity: O(n)

Because only one traversal / one loop is needed

Space Complexity: O(1)

Because no extra space is needed
Related Programs: