Explore
ProGrad Programs
About Us

Edit
Reply




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






If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in
Explore 'c plus plus'
Articles Practice Exercises