Find missing elements of a range
Last Updated :
14 Aug, 2023
Given an array, arr[0..n-1] of distinct elements and a range [low, high], find all numbers that are in a range, but not the array. The missing elements should be printed in sorted order.
Examples:
Input: arr[] = {10, 12, 11, 15},
low = 10, high = 15
Output: 13, 14
Input: arr[] = {1, 14, 11, 51, 15},
low = 50, high = 55
Output: 50, 52, 53, 54 55
Naive Approach:
The naive approach for the problem can be to use two nested loops: one to traverse numbers from low to high and other one to traverse entire array to find out whether the element of the outer loop exists in the array or not. If it doesn’t exist we will print it else continue to next iteration.
Algorithm:
- Traverse numbers from low to high using a for loop.
- For each number i in the range, initialize a boolean variable found to false.
- Traverse the array arr to check if i is present in the array.
- If i is found in arr, set found to true and break out of the loop.
- If i is not found in arr, print i.
- Repeat steps 2-5 for all numbers in the range [low, high].
C++
#include <bits/stdc++.h>
using namespace std;
void findMissing(int arr[], int n, int low, int high) {
for (int i = low; i <= high; i++) {
bool found = false;
for (int j = 0; j < n; j++) {
if (arr[j] == i) {
found = true;
break;
}
}
if (!found) {
cout << i << " ";
}
}
}
int main() {
int arr[] = { 1, 3, 5, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int low = 1, high = 10;
findMissing(arr, n, low, high);
return 0;
}
|
Java
import java.util.*;
public class GFG {
static void findMissing(int[] arr, int n, int low,
int high)
{
for (int i = low; i <= high; i++) {
boolean found = false;
for (int j = 0; j < n; j++) {
if (arr[j] == i) {
found = true;
break;
}
}
if (!found) {
System.out.print(i + " ");
}
}
}
public static void main(String[] args)
{
int[] arr = { 1, 3, 5, 4 };
int n = arr.length;
int low = 1, high = 10;
findMissing(arr, n, low, high);
}
}
|
Python3
def findMissing(arr, n, low, high):
for i in range(low, high+1):
found = False
for j in range(n):
if arr[j] == i:
found = True
break
if not found:
print(i, end=' ')
if __name__ == '__main__':
arr = [1, 3, 5, 4]
n = len(arr)
low = 1
high = 10
findMissing(arr, n, low, high)
|
C#
using System;
class GFG {
static void FindMissing(int[] arr, int n, int low,
int high)
{
for (int i = low; i <= high; i++) {
bool found = false;
for (int j = 0; j < n; j++) {
if (arr[j] == i) {
found = true;
break;
}
}
if (!found) {
Console.Write(i + " ");
}
}
}
static void Main()
{
int[] arr = { 1, 3, 5, 4 };
int n = arr.Length;
int low = 1, high = 10;
FindMissing(arr, n, low, high);
}
}
|
Javascript
function findMissing(arr, low, high) {
const missing = [];
for (let i = low; i <= high; i++) {
let found = false;
for (let j = 0; j < arr.length; j++) {
if (arr[j] === i) {
found = true;
break;
}
}
if (!found) {
missing.push(i);
}
}
for (let i = 0; i < missing.length; i++) {
console.log(missing[i] + " ");
}
}
const arr = [1, 3, 5, 4];
const low = 1, high = 10;
findMissing(arr, low, high);
|
Time Complexity: O( n * (high-low+1) ) as two nested for loops are executing with outer one from low to high and inner one from 1 to n where n is size of the input array.
Space Complexity: O(1) as no extra space has been taken.
There can be two approaches to solve the problem.
Use Sorting: Sort the array, then do a binary search for ‘low’. Once the location of low is found, start traversing the array from that location and keep printing all missing numbers.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
void printMissing(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 arr[] = { 1, 3, 5, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int low = 1, high = 10;
printMissing(arr, n, low, high);
return 0;
}
|
Java
import java.util.Arrays;
public class PrintMissing {
static void printMissing(int ar[], int low, int high)
{
Arrays.sort(ar);
int index = ceilindex(ar, low, 0, ar.length - 1);
int x = low;
while (index < ar.length && x <= high) {
if (ar[index] != x) {
System.out.print(x + " ");
}
else
index++;
x++;
}
while (x <= high) {
System.out.print(x + " ");
x++;
}
}
static int ceilindex(int ar[], int val, int low, int high)
{
if (val < ar[0])
return 0;
if (val > ar[ar.length - 1])
return ar.length;
int mid = (low + high) / 2;
if (ar[mid] == val)
return mid;
if (ar[mid] < val) {
if (mid + 1 < high && ar[mid + 1] >= val)
return mid + 1;
return ceilindex(ar, val, mid + 1, high);
}
else {
if (mid - 1 >= low && ar[mid - 1] < val)
return mid;
return ceilindex(ar, val, low, mid - 1);
}
}
public static void main(String[] args)
{
int arr[] = { 1, 3, 5, 4 };
int low = 1, high = 10;
printMissing(arr, low, high);
}
}
|
Python3
from bisect import bisect_left
def printMissing(arr, n, low, high):
arr.sort()
ptr = bisect_left(arr, low)
index = ptr
i = index
x = low
while (i < n and x <= high):
if(arr[i] != x):
print(x, end =" ")
else:
i = i + 1
x = x + 1
while (x <= high):
print(x, end =" ")
x = x + 1
arr = [1, 3, 5, 4]
n = len(arr)
low = 1
high = 10
printMissing(arr, n, low, high);
|
C#
using System;
class GFG {
static void printMissing(int[] ar,
int low, int high)
{
Array.Sort(ar);
int index = ceilindex(ar, low, 0,
ar.Length - 1);
int x = low;
while (index < ar.Length && x <= high) {
if (ar[index] != x) {
Console.Write(x + " ");
}
else
index++;
x++;
}
while (x <= high) {
Console.Write(x + " ");
x++;
}
}
static int ceilindex(int[] ar, int val,
int low, int high)
{
if (val < ar[0])
return 0;
if (val > ar[ar.Length - 1])
return ar.Length;
int mid = (low + high) / 2;
if (ar[mid] == val)
return mid;
if (ar[mid] < val) {
if (mid + 1 < high && ar[mid + 1] >= val)
return mid + 1;
return ceilindex(ar, val, mid + 1, high);
}
else {
if (mid - 1 >= low && ar[mid - 1] < val)
return mid;
return ceilindex(ar, val, low, mid - 1);
}
}
static public void Main()
{
int[] arr = { 1, 3, 5, 4 };
int low = 1, high = 10;
printMissing(arr, low, high);
}
}
|
Javascript
<script>
function printMissing(ar, low, high)
{
ar.sort();
let index = ceilindex(ar, low, 0, ar.length - 1);
let x = low;
while (index < ar.length && x <= high) {
if (ar[index] != x) {
document.write(x + " ");
}
else
index++;
x++;
}
while (x <= high) {
document.write(x + " ");
x++;
}
}
function ceilindex(ar, val, low, high)
{
if (val < ar[0])
return 0;
if (val > ar[ar.length - 1])
return ar.length;
let mid = Math.floor((low + high) / 2);
if (ar[mid] == val)
return mid;
if (ar[mid] < val) {
if (mid + 1 < high && ar[mid + 1] >= val)
return mid + 1;
return ceilindex(ar, val, mid + 1, high);
}
else {
if (mid - 1 >= low && ar[mid - 1] < val)
return mid;
return ceilindex(ar, val, low, mid - 1);
}
}
let arr = [ 1, 3, 5, 4 ];
let low = 1, high = 10;
printMissing(arr, low, high);
</script>
|
Time Complexity: O(n log n + k) where k is the number of missing elements
Auxiliary Space: O(n) or O(1) depending on the type of the array.
Using Arrays: Create a boolean array, where each index will represent whether the (i+low)th element is present in the array or not. Mark all those elements which are in the given range and are present in the array. Once all array items present in the given range have been marked true in the array, we traverse through the Boolean array and print all elements whose value is false.
Implementation:
C++14
#include <bits/stdc++.h>
using namespace std;
void printMissing(
int arr[], int n,
int low, int high)
{
bool points_of_range[high - low + 1] = { false };
for (int i = 0; i < n; i++) {
if (low <= arr[i] && arr[i] <= high)
points_of_range[arr[i] - low] = true;
}
for (int x = 0; x <= high - low; x++) {
if (points_of_range[x] == false)
cout << low + x << " ";
}
}
int main()
{
int arr[] = { 1, 3, 5, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int low = 1, high = 10;
printMissing(arr, n, low, high);
return 0;
}
|
Java
import java.util.Arrays;
public class Print {
static void printMissing(
int arr[], int low,
int high)
{
boolean[] points_of_range = new boolean
[high - low + 1];
for (int i = 0; i < arr.length; i++) {
if (low <= arr[i] && arr[i] <= high)
points_of_range[arr[i] - low] = true;
}
for (int x = 0; x <= high - low; x++) {
if (points_of_range[x] == false)
System.out.print((low + x) + " ");
}
}
public static void main(String[] args)
{
int arr[] = { 1, 3, 5, 4 };
int low = 1, high = 10;
printMissing(arr, low, high);
}
}
|
Python3
def printMissing(arr, n, low, high):
points_of_range = [False] * (high-low+1)
for i in range(n) :
if ( low <= arr[i] and arr[i] <= high ) :
points_of_range[arr[i]-low] = True
for x in range(high-low+1) :
if (points_of_range[x]==False) :
print(low+x, end = " ")
arr = [1, 3, 5, 4]
n = len(arr)
low, high = 1, 10
printMissing(arr, n, low, high)
|
C#
using System;
class GFG{
static void printMissing(int[] arr, int n,
int low, int high)
{
bool[] points_of_range = new bool[high - low + 1];
for(int i = 0; i < high - low + 1; i++)
points_of_range[i] = false;
for(int i = 0; i < n; i++)
{
if (low <= arr[i] && arr[i] <= high)
points_of_range[arr[i] - low] = true;
}
for(int x = 0; x <= high - low; x++)
{
if (points_of_range[x] == false)
Console.Write("{0} ", low + x);
}
}
public static void Main()
{
int[] arr = { 1, 3, 5, 4 };
int n = arr.Length;
int low = 1, high = 10;
printMissing(arr, n, low, high);
}
}
|
Javascript
<script>
function printMissing(
arr, low, high)
{
let points_of_range = Array(high - low + 1).fill(0);
for (let i = 0; i < arr.length; i++) {
if (low <= arr[i] && arr[i] <= high)
points_of_range[arr[i] - low] = true;
}
for (let x = 0; x <= high - low; x++) {
if (points_of_range[x] == false)
document.write((low + x) + " ");
}
}
let arr = [ 1, 3, 5, 4 ];
let low = 1, high = 10;
printMissing(arr, low, high);
</script>
|
Time Complexity: O(n + (high-low+1))
Auxiliary Space: O(n)
Use Hashing: Create a hash table and insert all array items into the hash table. Once all items are in hash table, traverse through the range and print all missing elements.
C++
#include <bits/stdc++.h>
using namespace std;
void printMissing(int arr[], int n, int low,
int high)
{
unordered_set<int> s;
for (int i = 0; i < n; i++)
s.insert(arr[i]);
for (int x = low; x <= high; x++)
if (s.find(x) == s.end())
cout << x << " ";
}
int main()
{
int arr[] = { 1, 3, 5, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int low = 1, high = 10;
printMissing(arr, n, low, high);
return 0;
}
|
Java
import java.util.Arrays;
import java.util.HashSet;
public class Print {
static void printMissing(int ar[], int low, int high)
{
HashSet<Integer> hs = new HashSet<>();
for (int i = 0; i < ar.length; i++)
hs.add(ar[i]);
for (int i = low; i <= high; i++) {
if (!hs.contains(i)) {
System.out.print(i + " ");
}
}
}
public static void main(String[] args)
{
int arr[] = { 1, 3, 5, 4 };
int low = 1, high = 10;
printMissing(arr, low, high);
}
}
|
Python3
def printMissing(arr, n, low, high):
s = set(arr)
for x in range(low, high + 1):
if x not in s:
print(x, end = ' ')
arr = [1, 3, 5, 4]
n = len(arr)
low, high = 1, 10
printMissing(arr, n, low, high)
|
C#
using System;
using System.Collections.Generic;
class GFG {
static void printMissing(int[] arr, int n,
int low, int high)
{
HashSet<int> s = new HashSet<int>();
for (int i = 0; i < n; i++) {
s.Add(arr[i]);
}
for (int x = low; x <= high; x++)
if (!s.Contains(x))
Console.Write(x + " ");
}
public static void Main()
{
int[] arr = { 1, 3, 5, 4 };
int n = arr.Length;
int low = 1, high = 10;
printMissing(arr, n, low, high);
}
}
|
Javascript
<script>
function printMissing(ar, low, high) {
let hs = new Set();
for (let i = 0; i < ar.length; i++)
hs.add(ar[i]);
for (let i = low; i <= high; i++) {
if (!hs.has(i)) {
document.write(i + " ");
}
}
}
let arr = [1, 3, 5, 4];
let low = 1, high = 10;
printMissing(arr, low, high);
</script>
|
Time Complexity: O(n + (high-low+1))
Auxiliary Space: O(n)
Which approach is better?
The time complexity of the first approach is O(nLogn + k) where k is the number of missing elements (Note that k may be more than n Log n if the array is small and the range is big)
The time complexity of the second and third solutions is O(n + (high-low+1)).
If the given array has almost all elements of the range, i.e., n is close to the value of (high-low+1), then the second and third approaches are definitely better as there is no Log n factor. But if n is much smaller than the range, then the first approach is better as it doesn’t require extra space for hashing. We can also modify the first approach to print adjacent missing elements as range to save time. For example, if 50, 51, 52, 53, 54, 59 are missing, we can print them as 50-54, 59 in the first method. And if printing this way is allowed, the first approach takes only O(n Log n) time. Out of the Second and Third Solutions, the second solution is better because the worst-case time complexity of the second solution is better than the third.
Piyush Gupta and Shubh Bansal
Please Login to comment...