Explore

Edit

Edit

Find all the Missing Elements of a Range | FACE Prep

Published on 10 Mar 2020

Program to find all the missing elements in the given range is discussed here. In this program, we have two inputs:

• An array of integers
• The start value and end value of the range

The elements that are missing within the specified range is the expected output. For example, consider the array: arr = {1, 2, 3, 8, 9}. The start value is 1 and the end value is 5. This means the range is 1 to 5. Here the missing elements are 4 and 5.

Method 1: By using sorting

• Sort the array
• Perform a binary search for finding start_value.
• Once the location of start_value is found, traverse the array from that location print all missing numbers until the end value.

Program to find all the missing elements of a range (using sorting)

C++
Java

Output
Enter the number of elements : 5
Input the array elements : 1 2 3 8 9
Enter the start and end value : 1 5
Missing numbers : 4 5

Time complexity: O(nLogn + k)

Method 2: By using hashing

• Create a hash table.
• Traverse through the array and update the table.
• Now, again traverse the array, find all the missing elements from the range specified.

Program to find all the missing elements of a range (using hashing)

C++
Java
Python 3

Output
Enter the number of elements : 5
Input the array elements : 1 2 3 8 9
Enter the start and end value : 1 5
Missing numbers : 4 5

Time complexity: O(n + (high-low+1)).

Recommended Programs