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.

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**:

- Python Program to Find the Odd Occurring Element in an Array/list
- Python Program to Find the Second Largest Number in a List
- Python Program to Move all Zeros present in an Array/List to the End
- Python Program to Find a Pair with the Given Sum in an Array
- Python Program to Find all Numbers in a Range which are Perfect Squares and Sum of all Digits in the Number is Less than 10
- Python Program to Find the Largest Number in a List
- Python Program to Find the Factorial of a Number