Find all the missing elements of a range | faceprep

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++ program to find all the missing elements in a range 

#include<bits/stdc++.h>
using namespace std;

void print_missing_numbers(int arr[], int n, int low, int high)
{
sort(arr, arr+n);

int *ptr = lower_bound(arr, arr+n, low);
int index = ptr – arr;

int i = index, x = low;
while (i < n && x<=high)
{
if (arr[i] != x)
cout << x << ” “;

else
i++;
x++;
}

while (x <= high)
cout << x++ << ” “;
}

int main()
{
int n, low, high;
cout << “\nEnter the number of elements : “;
cin >> n;
int arr[n];
cout << “\nInput the array elements : “;
for(int i = 0; i < n; i++)
{
cin >> arr[i];
}
cout << “\nEnter the start and end values : “;
cin >> low >> high;
cout << “\nMissing numbers : “;
print_missing_numbers(arr, n, low, high);
cout << endl;
return 0;
}

// Java program to find all the missing elements in a range 

import java.util.Arrays;

public class Main
{

static void print_missing_elements(int ar[], int start, int end)
{
Arrays.sort(ar);
int index = ceil_index(ar, start, 0, ar.length – 1);
int x = start;

while (index < ar.length && x <= end)
{

if (ar[index] != x)
{
System.out.print(x + ” “);
}

else
index++;
x++;
}

while (x <= end)
{
System.out.print(x + ” “);
x++;
}

}

static int ceil_index(int ar[], int val, int start, int end)
{

if (val < ar[0])
return 0;
if (val > ar[ar.length – 1])
return ar.length;

int mid = (start + end) / 2;
if (ar[mid] == val)
return mid;
if (ar[mid] < val)
{
if (mid + 1 < end && ar[mid + 1] >= val)
return mid + 1;
return ceil_index(ar, val, mid + 1, end);
}
else
{
if (mid – 1 >= start && ar[mid – 1] < val)
return mid;
return ceil_index(ar, val, start, mid – 1);
}

}

public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 8, 9};
int start = 1, end = 5;
System.out.print(“\nMissing elements : ” );
print_missing_elements(arr, start, end);
}
}

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++ program to find all the missing elements in a range

#include<bits/stdc++.h>
using namespace std;

void print_missing_numbers(int arr[], int n, int low, int high)
{
sort(arr, arr+n);

int *ptr = lower_bound(arr, arr+n, low);
int index = ptr – arr;

int i = index, x = low;
while (i < n && x<=high)
{
if (arr[i] != x)
cout << x << ” “;

else
i++;
x++;
}

while (x <= high)
cout << x++ << ” “;
}

int main()
{
int n, low, high;
cout << “\nEnter the number of elements : “;
cin >> n;
int arr[n];
cout << “\nInput the array elements : “;
for(int i = 0; i < n; i++)
{
cin >> arr[i];
}
cout << “\nEnter the start and end values : “;
cin >> low >> high;
cout << “\nMissing numbers : “;
print_missing_numbers(arr, n, low, high);
cout << endl;
return 0;
}

// Java program to find all the missing elements in a range

import java.util.Arrays;
import java.util.HashSet;

public class Main
{
static void print_missing_elements(int ar[], int start, int end)
{
HashSet<Integer> hs = new HashSet<>();

for (int i = 0; i < ar.length; i++)
hs.add(ar[i]);

for (int i = start; i <= end; i++)
{
if (!hs.contains(i))
{
System.out.print(i + ” “);
}
}
}

public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 8, 9 };
int start = 1, end = 5;
System.out.print(“Missing elements : ” );
print_missing_elements(arr, start, end);
}
}

# Python program to find all the missing elements in a range

def print_missing_elements(arr, n, start, end):
s = set(arr)
for x in range(start, end + 1):
if x not in s:
print(x, end = ‘ ‘)

arr = [1, 2, 3, 8, 9]
n = len(arr)
start, end = 1, 5
print(“Missing elements :”,end=” “)
print_missing_elements(arr, n, start, end)

Output:

missing elements in a range

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