Find missing elements of a range in C++

In this tutorial, we will learn how to find missing elements of a range in C++. Here, we will be given an array of elements and two numbers. We will have to find all the missing numbers in that range whether present in the array or not.

C++ Program to find all the missing elements in an array for a given range

According to the given question, let’s take an example:

Case 1:

Array = {20,26,18,23,1,45,32,24,33,50,55}
Range = 21 - 35
Missing = 21,22,25,27,28,29,31,34,35

Hence, we should write our program in such a way that it deals with the above-stated example where the lower bound is greater than the lowest element in the array and the higher bound is lower than the highest element in the array.

Case 2:

Array = {20,26,18,23,1,45,32,24,33,50,55}
Range = 11 - 35
Missing = 11,12,13,14,15,16,17,19,21,22,25,27,28,29,31,34,35

Hence, our algorithm should also deal with the case where the lower bound is less than the lowest element in the array and the higher bound is lower than the highest element in the array.

Case 3:

Array = {20,26,18,23,1,45,32,24,33,40,38,42,41}
Range = 21 - 48
Missing = 21 22 25 27 28 29 30 31 34 35 36 37 39 43 44 46 47 48

Hence, the algorithm should also deal with the case in which lower bound is greater than the lowest element but the higher bound is also greater than the highest element in the array.

Our approach to this problem is very simple, we will first sort the algorithm using the sort method present in STL in C++. Then we will search for lower bound in our algorithm using the binary search algorithm. Then we start traversing our array from that element, if the next number is present in the array we will increment the number, if not present we will print it out and the loop will run till either we are out of bounds of the array or we reach higher bound. So this is the simplest approach to solve the given program. Now let us code for the above-explained problem and procedure.

Code for the algorithm:

#include <bits/stdc++.h> 
using namespace std; 
  
// Print all elements of range [low, high] that 
// are not present in arr[0..n-1] 
void printMissingItems(int array[], int n, int low, 
                  int high) 
{ 
    // Sort the array 
    sort(array, array + n); 
  
    // finding lower bound
    int* ptr = lower_bound(array, array + n, low); 
    int lowerIndex = ptr - array; 
  
    //start from lower index and traverse
    int i = lowerIndex, x = low ;
    while (i < n && x <= high) { 
        // If x doesn't match print 
        if (array[i] != x) 
            cout << x << " "; 
  
        // If x matches, move to next element in array 
        else
            i++; 
  
        // Move to next element in range [low, high] 
        x++; 
    } 
  
    // Print range elements thar are greater than the 
    // last element of sorted array. 
    while (x <= high) 
        cout << x++ << " "; 
} 
  
// Main program 
int main() 
{ 
    int array[] ={20,26,18,23,1,45,32,24,33,50,55}; 
    int n = sizeof(array) / sizeof(array[0]); 
    int low = 21, high = 35; 
    count<<"MISSING NUMBERS ARE"<<endl;
    printMissingItems(array, n, low, high); 
    return 0; 
}

Output:

MISSING NUMBERS ARE
21 22 25 27 28 29 30 31 34 35

Hence, we have found the solution to the given problem. I hope this tutorial will clear all your doubts.

Thank You.

Leave a Reply