Last Updated: 30 Sep, 2020
Day 19 : Missing Numbers
Easy
Asked in companies
You are given an array 'ARR' of distinct positive integers. You need to find all numbers that are in the range of the elements of the array, but not in the array. The missing elements should be printed in sorted order.
Example:
If the given array is [4, 2, 9] then you should print "3 5 6 7 8". As all these elements lie in the range but not present in the array.
Input Format:
The first line of input contains a single integer 'T', representing the number of test cases.
The first line of input contains an integer 'N' representing the length of the array.
The next line contains 'N' single space-separated integers representing elements of the array 'ARR'.
Output Format :
For each test case, return the list of elements that are not in the array 'ARR'.
Print the output of each test case in a separate line.
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^5
0 <= 'ARR[i]' <= 150000
Where 'ARR[i]' denotes the array element.
Time Limit: 1 sec
Approaches
The steps are as follows:
- Get the minimum and maximum elements of the array.
- Initialise a list of data type integers, which will store all the missing numbers between the minimum and maximum elements.
- For every element between the minimum and maximum number, check whether it is present in the array or not by using linear search.
- If it is present, then continue, otherwise add the number in the list.
- Finally, return the list.
The steps are as follows:
- Sort the array in increasing order.
- Get the minimum element ('ARR[0]') and the maximum element ('ARR['N' - 1]') of the array.
- Initialise a list of data type integers, which will store all the missing numbers between the minimum and maximum elements.
- Run a loop from minimum element to maximum element, check if the current number is not equal to the element of the array then add the number in the list, otherwise increment the current index of the array.
- Finally, return the list.
The steps are as follows:
- Create a set of integers, which will store the elements of the array.
- Get the minimum and maximum elements of the array.
- Initialise a list of integer data type integers, which will store all the missing numbers between the minimum and maximum elements.
- Store all the elements of the array in the set.
- Run a loop from the minimum element to maximum element, and check if it is present in the set or not.
- If it is present then continue otherwise add the number in the list.
- Finally, return the list.