The problem Find missing elements of a range” states that you are given an array of distinct elements within a particular range and a range given as low and high. Find all the missing elements within a range which is not present in an array. The output should be in sorted order.

Table of Contents

## Example

arr[] = [1, 3, 5, 7, 8, 9] low=1 high = 10

2, 4, 6, 10

**Explanation**

These are the missing numbers in the array within the range given as low and high i.e., 1 and 10.

arr[] = [2, 3, 7, 8] low=1 high = 9

1, 4, 5, 6, 9

**Explanation**

These are the missing numbers in the array within the range given as low and high i.e., 1 and 10.

## Algorithm

- Declare a set.
- Traverse the array and put all the elements into the set.
- While “i” is equal to low and “i” is less than equal to high.
- If a set does not contain “i”.
- Print āiā.

- If a set does not contain “i”.

### Explanation

We are given a problem statement that asks to find out all the missing elements in an array within a given range as low and high. To solve this we will use a set and going to store the values into the set of the given array. We are given a range as low and a high, we have to print all the elements within a low and a high inclusively.

To get that order we already store the array elements into the set. We need to run a loop initializing āiā as low. we run the loop until the value of āiā becomes high. Then check if the set does not contain the value āiā then print āi’. Hence we will get all the elements that are missing from an array within a given range. Let us consider an example.

arr []={2, 3, 7, 8} low=1, high = 9

We need to traverse the array and put all the elements of an array into the set. Our set will become

set=[2,3,7,8]

In a loop initialize i to low and loop runs until high, it means āiā is equal to low = 1 and high =9

i=1, if the set does not contain i, prints 1

[ 1]

i=2, set has a value ā2ā and does nothing.

i=3, set has a value ā3ā and does nothing.

i=4, if the set does not contain i, prints 4

[1, 4]

i=5, if the set does not contain i, prints 5

[1, 4, 5]

i=6, if the set does not contain i, prints 6

[1, 4, 5, 6]

i=7, set has a value ā7ā and does nothing.

i=8, set has a value ā8ā and does nothing.

i=9, if the set does not contain i, prints 1

[1, 4, 5, 6, 9]

Our output will become: [1, 4, 5, 6, 9]

## Code

### C++ code to Find missing elements of a range

#include <unordered_set> #include<iostream> using namespace std; void getMissingElements(int arr[], int n, int low, int high) { unordered_set<int> myset; for (int i = 0; i < n; i++) myset.insert(arr[i]); for (int x = low; x <= high; x++) if (myset.find(x) == myset.end()) cout << x << " "; } int main() { int arr[] = { 2,3,7,8 }; int low = 1, high = 9; int n = sizeof(arr) / sizeof(arr[0]); getMissingElements(arr, n, low, high); return 0; }

1 4 5 6 9

### Java code to Find missing elements of a range

import java.util.HashSet; class RangeMissingElements { public static void getMissingElements(int arr[], int low, int high) { HashSet<Integer> myset = new HashSet<>(); for (int i = 0; i < arr.length; i++) { myset.add(arr[i]); } for (int i = low; i <= high; i++) { if (!myset.contains(i)) { System.out.print(i + " "); } } } public static void main(String[] args) { int arr[] = {2,3,7,8}; int low = 1, high = 9; getMissingElements(arr, low, high); } }

1 4 5 6 9

## Complexity Analysis

### Time Complexity

**O(n + (high-low+1))Ā **whereĀ **“n”** is the number of elements present in the array,** “high” **andĀ **“low” **is the input provided.

### Space Complexity

**O(n),Ā **in the worst case, if all elements are distinct. We’ll have to store all the elements. Thus making the algorithm require linear time.