Write a Python Program to Find the Missing Element from the Given List

In this tutorial, we will write program to find the missing element from the given list within the range of 1 to N.

Problem Statement

The problem statement is given an array of size N-1 such that it only contains distinct integers in the range of 1 to N. Find the missing element.

Example - 1

Input:

N = 5

A = [1,2,3,5]

Output:

Example - 2:

Input:

N = 10

A = [6,1,2,8,3,4,7,10,5]

Output:

Solution

We can solve this problem using the two approaches. Let's see the first approach.

Approach - 1: Sum of Integers

We can follow the below steps -

Calculate the sum of integers from 1 to N using the formula: sum = N*(N+1)/2
Traverse the array and calculate the sum of all elements in the array.
Subtract the sum of the array obtained in step 2 from the sum of integers obtained in step 1.
We will get the missing element.

Let's see the following code.

Example -

def find_missing_element(n, arr):
    total_sum = n*(n+1)//2  # calculate sum of integers from 1 to N
    arr_sum = sum(arr)  # calculate sum of array elements
    missing_element = total_sum - arr_sum  # calculate missing element
    return missing_element
print("The missing element is:", find_missing_element(5, [1, 2, 3, 5]))

Output:

The missing element is: 4

Explanation -

The above code, we create the find_missing_element() function which takes length of list and list of integer as arguments. We calculates the sum of integers from 1 to N using the formula, then sums the elements of the array to find the missing element by subtracting the sum of the array from the sum of integers. This solution has a time complexity of O(N) since it requires traversing the entire array.

Approach -2: Binary Search

We will solve this problem using the binary search algorithm. Below are the steps.

First, we sort the given array in ascending order.
Initialize two pointers, left and right, to the first and last indices of the array, respectively.
While left <= right, do the following:
Calculate the middle index mid as (left + right) // 2.
If the value at mid is equal to mid + 1, the missing element is in the right half of the array. Move the left pointer to mid + 1.
Otherwise, the missing element is in the left half of the array. Move the right pointer to mid - 1.
At the end of the loop, the value at left (or right, they are the same) will be the missing element.

Let's see the following Python code.

Example -

def find_missing_element_optimized(n, arr):
    arr.sort()  # sort the array in ascending order
    left, right = 0, n - 1  # initialize left and right pointers
    while left <= right:
        mid = (left + right) // 2  # calculate middle index
        if arr[mid] == mid + 1:  # missing element is in the right half
            left = mid + 1
        else:  # missing element is in the left half
            right = mid - 1
    return left + 1  # return the missing element

print("The missing element is:", find_missing_element_optimized(10, [6,1,2,8,3,4,7,10,5]))

Output:

The missing element is: 9

Explanation -

The optimized solution uses binary search to find the missing element more efficiently.

We first sort the array in ascending order, then initialize two pointers, left and right, to the first and last indices of the array, respectively.

We then calculate the middle index and determine whether the missing element is in the left or right half of the array.

We repeat this process until we find the missing element, which will be at the index pointed to by the left. This solution has a time complexity of O(log N) since we eliminate half of the array at each iteration.

Next TopicWrite Python Program to Check Whether a Given Linked List is Palindrome

← prev next →