# Find missing elements of a range

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:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

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

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.

## C++

`// A sorting based C++ program to find missing` `// elements from an array` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Print all elements of range [low, high] that` `// are not present in arr[0..n-1]` `void` `printMissing(` `int` `arr[], ` `int` `n, ` `int` `low,` ` ` `int` `high)` `{` ` ` `// Sort the array` ` ` `sort(arr, arr + n);` ` ` `// Do binary search for 'low' in sorted` ` ` `// array and find index of first element` ` ` `// which either equal to or greater than` ` ` `// low.` ` ` `int` `* ptr = lower_bound(arr, arr + n, low);` ` ` `int` `index = ptr - arr;` ` ` `// Start from the found index and linearly` ` ` `// search every range element x after this` ` ` `// index in arr[]` ` ` `int` `i = index, x = low;` ` ` `while` `(i < n && x <= high) {` ` ` `// If x doesn't math with current element` ` ` `// print it` ` ` `if` `(arr[i] != x)` ` ` `cout << x << ` `" "` `;` ` ` `// If x matches, move to next element in arr[]` ` ` `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++ << ` `" "` `;` `}` `// Driver program` `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

`// A sorting based Java program to find missing` `// elements from an array` `import` `java.util.Arrays;` `public` `class` `PrintMissing {` ` ` `// Print all elements of range [low, high] that` ` ` `// are not present in arr[0..n-1]` ` ` `static` `void` `printMissing(` `int` `ar[], ` `int` `low, ` `int` `high)` ` ` `{` ` ` `Arrays.sort(ar);` ` ` `// Do binary search for 'low' in sorted` ` ` `// array and find index of first element` ` ` `// which either equal to or greater than` ` ` `// low.` ` ` `int` `index = ceilindex(ar, low, ` `0` `, ar.length - ` `1` `);` ` ` `int` `x = low;` ` ` `// Start from the found index and linearly` ` ` `// search every range element x after this` ` ` `// index in arr[]` ` ` `while` `(index < ar.length && x <= high) {` ` ` `// If x doesn't math with current element` ` ` `// print it` ` ` `if` `(ar[index] != x) {` ` ` `System.out.print(x + ` `" "` `);` ` ` `}` ` ` `// If x matches, move to next element in arr[]` ` ` `else` ` ` `index++;` ` ` `// 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) {` ` ` `System.out.print(x + ` `" "` `);` ` ` `x++;` ` ` `}` ` ` `}` ` ` `// Utility function to find ceil index of given element` ` ` `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` `);` ` ` `}` ` ` `}` ` ` `// Driver program to test above function` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `arr[] = { ` `1` `, ` `3` `, ` `5` `, ` `4` `};` ` ` `int` `low = ` `1` `, high = ` `10` `;` ` ` `printMissing(arr, low, high);` ` ` `}` `}` `// This code is contributed by Rishabh Mahrsee` |

## Python

`# Python library for binary search` `from` `bisect ` `import` `bisect_left` `# A sorting based C++ program to find missing` `# elements from an array` `# Print all elements of range [low, high] that` `# are not present in arr[0..n-1]` `def` `printMissing(arr, n, low, high):` ` ` ` ` `# Sort the array` ` ` `arr.sort()` ` ` ` ` `# Do binary search for 'low' in sorted` ` ` `# array and find index of first element` ` ` `# which either equal to or greater than` ` ` `# low.` ` ` `ptr ` `=` `bisect_left(arr, low)` ` ` `index ` `=` `ptr` ` ` ` ` `# Start from the found index and linearly` ` ` `# search every range element x after this` ` ` `# index in arr[]` ` ` `i ` `=` `index` ` ` `x ` `=` `low` ` ` `while` `(i < n ` `and` `x <` `=` `high):` ` ` `# If x doesn't math with current element` ` ` `# print it` ` ` `if` `(arr[i] !` `=` `x):` ` ` `print` `(x, end ` `=` `" "` `)` ` ` `# If x matches, move to next element in arr[]` ` ` `else` `:` ` ` `i ` `=` `i ` `+` `1` ` ` `# Move to next element in range [low, high]` ` ` `x ` `=` `x ` `+` `1` ` ` `# Print range elements thar are greater than the` ` ` `# last element of sorted array.` ` ` `while` `(x <` `=` `high):` ` ` `print` `(x, end ` `=` `" "` `)` ` ` `x ` `=` `x ` `+` `1` `# Driver code` `arr ` `=` `[` `1` `, ` `3` `, ` `5` `, ` `4` `]` `n ` `=` `len` `(arr)` `low ` `=` `1` `high ` `=` `10` `printMissing(arr, n, low, high);` `# This code is contributed by YatinGupta` |

## C#

`// A sorting based Java program to` `// find missing elements from an array` `using` `System;` `class` `GFG {` ` ` `// Print all elements of range` ` ` `// [low, high] that are not` ` ` `// present in arr[0..n-1]` ` ` `static` `void` `printMissing(` `int` `[] ar,` ` ` `int` `low, ` `int` `high)` ` ` `{` ` ` `Array.Sort(ar);` ` ` `// Do binary search for 'low' in sorted` ` ` `// array and find index of first element` ` ` `// which either equal to or greater than` ` ` `// low.` ` ` `int` `index = ceilindex(ar, low, 0,` ` ` `ar.Length - 1);` ` ` `int` `x = low;` ` ` `// Start from the found index and linearly` ` ` `// search every range element x after this` ` ` `// index in arr[]` ` ` `while` `(index < ar.Length && x <= high) {` ` ` `// If x doesn't math with current` ` ` `// element print it` ` ` `if` `(ar[index] != x) {` ` ` `Console.Write(x + ` `" "` `);` ` ` `}` ` ` `// If x matches, move to next` ` ` `// element in arr[]` ` ` `else` ` ` `index++;` ` ` `// 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) {` ` ` `Console.Write(x + ` `" "` `);` ` ` `x++;` ` ` `}` ` ` `}` ` ` `// Utility function to find` ` ` `// ceil index of given element` ` ` `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);` ` ` `}` ` ` `}` ` ` `// Driver Code` ` ` `static` `public` `void` `Main()` ` ` `{` ` ` `int` `[] arr = { 1, 3, 5, 4 };` ` ` `int` `low = 1, high = 10;` ` ` `printMissing(arr, low, high);` ` ` `}` `}` `// This code is contributed` `// by Sach_Code` |

**Output: **

2 6 7 8 9 10

**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.

## C++14

`// An array based C++ program` `// to find missing elements from` `// an array` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Print all elements of range` `// [low, high] that are not present` `// in arr[0..n-1]` `void` `printMissing(` ` ` `int` `arr[], ` `int` `n,` ` ` `int` `low, ` `int` `high)` `{` ` ` `// Create boolean array of size` ` ` `// high-low+1, each index i representing` ` ` `// whether (i+low)th element found or not.` ` ` `bool` `points_of_range[high - low + 1] = { ` `false` `};` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `// if ith element of arr is in` ` ` `// range low to high then mark` ` ` `// corresponding index as true in array` ` ` `if` `(low <= arr[i] && arr[i] <= high)` ` ` `points_of_range[arr[i] - low] = ` `true` `;` ` ` `}` ` ` `// Traverse through the range and` ` ` `// print all elements whose value` ` ` `// is false` ` ` `for` `(` `int` `x = 0; x <= high - low; x++) {` ` ` `if` `(points_of_range[x] == ` `false` `)` ` ` `cout << low + x << ` `" "` `;` ` ` `}` `}` `// Driver program` `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;` `}` `// This code is contributed by Shubh Bansal` |

## Java

`// An array based Java program` `// to find missing elements from` `// an array` `import` `java.util.Arrays;` `public` `class` `Print {` ` ` `// Print all elements of range` ` ` `// [low, high] that are not present` ` ` `// in arr[0..n-1]` ` ` `static` `void` `printMissing(` ` ` `int` `arr[], ` `int` `low,` ` ` `int` `high)` ` ` `{` ` ` `// Create boolean array of` ` ` `// size high-low+1, each index i` ` ` `// representing whether (i+low)th` ` ` `// element found or not.` ` ` `boolean` `[] points_of_range = ` `new` `boolean` ` ` `[high - low + ` `1` `];` ` ` `for` `(` `int` `i = ` `0` `; i < arr.length; i++) {` ` ` `// if ith element of arr is in` ` ` `// range low to high then mark` ` ` `// corresponding index as true in array` ` ` `if` `(low <= arr[i] && arr[i] <= high)` ` ` `points_of_range[arr[i] - low] = ` `true` `;` ` ` `}` ` ` `// Traverse through the range and print all` ` ` `// elements whose value is false` ` ` `for` `(` `int` `x = ` `0` `; x <= high - low; x++) {` ` ` `if` `(points_of_range[x] == ` `false` `)` ` ` `System.out.print((low + x) + ` `" "` `);` ` ` `}` ` ` `}` ` ` `// Driver program to test above function` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `arr[] = { ` `1` `, ` `3` `, ` `5` `, ` `4` `};` ` ` `int` `low = ` `1` `, high = ` `10` `;` ` ` `printMissing(arr, low, high);` ` ` `}` `}` `// This code is contributed by Shubh Bansal` |

## Python3

`# An array-based Python3 program to` `# find missing elements from an array` `# Print all elements of range` `# [low, high] that are not` `# present in arr[0..n-1]` `def` `printMissing(arr, n, low, high):` ` ` `# Create boolean list of size` ` ` `# high-low+1, each index i` ` ` `# representing whether (i+low)th` ` ` `# element found or not.` ` ` `points_of_range ` `=` `[` `False` `] ` `*` `(high` `-` `low` `+` `1` `)` ` ` ` ` `for` `i ` `in` `range` `(n) :` ` ` `# if ith element of arr is in range` ` ` `# low to high then mark corresponding` ` ` `# index as true in array` ` ` `if` `( low <` `=` `arr[i] ` `and` `arr[i] <` `=` `high ) :` ` ` `points_of_range[arr[i]` `-` `low] ` `=` `True` ` ` `# Traverse through the range` ` ` `# and print all elements whose value` ` ` `# is false` ` ` `for` `x ` `in` `range` `(high` `-` `low` `+` `1` `) :` ` ` `if` `(points_of_range[x]` `=` `=` `False` `) :` ` ` `print` `(low` `+` `x, end ` `=` `" "` `)` `# Driver Code` `arr ` `=` `[` `1` `, ` `3` `, ` `5` `, ` `4` `]` `n ` `=` `len` `(arr)` `low, high ` `=` `1` `, ` `10` `printMissing(arr, n, low, high)` `# This code is contributed` `# by Shubh Bansal` |

## C#

`// An array based C# program` `// to find missing elements from` `// an array` `using` `System;` `class` `GFG{` `// Print all elements of range` `// [low, high] that are not present` `// in arr[0..n-1]` `static` `void` `printMissing(` `int` `[] arr, ` `int` `n,` ` ` `int` `low, ` `int` `high)` `{` ` ` ` ` `// Create boolean array of size` ` ` `// high-low+1, each index i representing` ` ` `// whether (i+low)th element found or not.` ` ` `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 ith element of arr is in` ` ` `// range low to high then mark` ` ` `// corresponding index as true in array` ` ` `if` `(low <= arr[i] && arr[i] <= high)` ` ` `points_of_range[arr[i] - low] = ` `true` `;` ` ` `}` ` ` `// Traverse through the range and` ` ` `// print all elements whose value` ` ` `// is false` ` ` `for` `(` `int` `x = 0; x <= high - low; x++)` ` ` `{` ` ` `if` `(points_of_range[x] == ` `false` `)` ` ` `Console.Write(` `"{0} "` `, low + x);` ` ` `}` `}` `// Driver code` `public` `static` `void` `Main()` `{` ` ` `int` `[] arr = { 1, 3, 5, 4 };` ` ` `int` `n = arr.Length;` ` ` `int` `low = 1, high = 10;` ` ` ` ` `printMissing(arr, n, low, high);` `}` `}` `// This code is contributed by subhammahato348` |

## Javascript

`<script>` `// Javascript program to find missing elements from` `// an array` `// Prlet all elements of range` ` ` `// [low, high] that are not present` ` ` `// in arr[0..n-1]` ` ` `function` `prletMissing(` ` ` `arr, low, high)` ` ` `{` ` ` `// Create boolean array of` ` ` `// size high-low+1, each index i` ` ` `// representing whether (i+low)th` ` ` `// element found or not.` ` ` `let polets_of_range = Array(high - low + 1).fill(0); ` ` ` ` ` `for` `(let i = 0; i < arr.length; i++) {` ` ` `// if ith element of arr is in` ` ` `// range low to high then mark` ` ` `// corresponding index as true in array` ` ` `if` `(low <= arr[i] && arr[i] <= high)` ` ` `polets_of_range[arr[i] - low] = ` `true` `;` ` ` `}` ` ` ` ` `// Traverse through the range and print all` ` ` `// elements whose value is false` ` ` `for` `(let x = 0; x <= high - low; x++) {` ` ` `if` `(polets_of_range[x] == ` `false` `)` ` ` `document.write((low + x) + ` `" "` `);` ` ` `}` ` ` `}` `// Driver program` ` ` `let arr = [ 1, 3, 5, 4 ];` ` ` `let low = 1, high = 10;` ` ` `prletMissing(arr, low, high);` ` ` `</script>` |

**Output:**

2 6 7 8 9 10

**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++

`// A hashing based C++ program to find missing` `// elements from an array` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Print all elements of range [low, high] that` `// are not present in arr[0..n-1]` `void` `printMissing(` `int` `arr[], ` `int` `n, ` `int` `low,` ` ` `int` `high)` `{` ` ` `// Insert all elements of arr[] in set` ` ` `unordered_set<` `int` `> s;` ` ` `for` `(` `int` `i = 0; i < n; i++)` ` ` `s.insert(arr[i]);` ` ` `// Traverse throught the range an print all` ` ` `// missing elements` ` ` `for` `(` `int` `x = low; x <= high; x++)` ` ` `if` `(s.find(x) == s.end())` ` ` `cout << x << ` `" "` `;` `}` `// Driver program` `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

`// A hashing based Java program to find missing` `// elements from an array` `import` `java.util.Arrays;` `import` `java.util.HashSet;` `public` `class` `Print {` ` ` `// Print all elements of range [low, high] that` ` ` `// are not present in arr[0..n-1]` ` ` `static` `void` `printMissing(` `int` `ar[], ` `int` `low, ` `int` `high)` ` ` `{` ` ` `HashSet<Integer> hs = ` `new` `HashSet<>();` ` ` `// Insert all elements of arr[] in set` ` ` `for` `(` `int` `i = ` `0` `; i < ar.length; i++)` ` ` `hs.add(ar[i]);` ` ` `// Traverse throught the range an print all` ` ` `// missing elements` ` ` `for` `(` `int` `i = low; i <= high; i++) {` ` ` `if` `(!hs.contains(i)) {` ` ` `System.out.print(i + ` `" "` `);` ` ` `}` ` ` `}` ` ` `}` ` ` `// Driver program to test above function` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `arr[] = { ` `1` `, ` `3` `, ` `5` `, ` `4` `};` ` ` `int` `low = ` `1` `, high = ` `10` `;` ` ` `printMissing(arr, low, high);` ` ` `}` `}` `// This code is contributed by Rishabh Mahrsee` |

## Python3

`# A hashing based Python3 program to` `# find missing elements from an array` `# Print all elements of range` `# [low, high] that are not` `# present in arr[0..n-1]` `def` `printMissing(arr, n, low, high):` ` ` `# Insert all elements of` ` ` `# arr[] in set` ` ` `s ` `=` `set` `(arr)` ` ` `# Traverse through the range` ` ` `# and print all missing elements` ` ` `for` `x ` `in` `range` `(low, high ` `+` `1` `):` ` ` `if` `x ` `not` `in` `s:` ` ` `print` `(x, end ` `=` `' '` `)` `# Driver Code` `arr ` `=` `[` `1` `, ` `3` `, ` `5` `, ` `4` `]` `n ` `=` `len` `(arr)` `low, high ` `=` `1` `, ` `10` `printMissing(arr, n, low, high)` `# This code is contributed` `# by SamyuktaSHegde` |

## C#

`// A hashing based C# program to` `// find missing elements from an array` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG {` ` ` `// Print all elements of range` ` ` `// [low, high] that are not` ` ` `// present in arr[0..n-1]` ` ` `static` `void` `printMissing(` `int` `[] arr, ` `int` `n,` ` ` `int` `low, ` `int` `high)` ` ` `{` ` ` `// Insert all elements of arr[] in set` ` ` `HashSet<` `int` `> s = ` `new` `HashSet<` `int` `>();` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `s.Add(arr[i]);` ` ` `}` ` ` `// Traverse throught the range` ` ` `// an print all missing elements` ` ` `for` `(` `int` `x = low; x <= high; x++)` ` ` `if` `(!s.Contains(x))` ` ` `Console.Write(x + ` `" "` `);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main()` ` ` `{` ` ` `int` `[] arr = { 1, 3, 5, 4 };` ` ` `int` `n = arr.Length;` ` ` `int` `low = 1, high = 10;` ` ` `printMissing(arr, n, low, high);` ` ` `}` `}` `// This code is contributed by ihritik` |

**Output:**

2 6 7 8 9 10

**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 nLogn 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.

This article is contributed by **Piyush Gupta** and **Shubh Bansal**. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above