Day 19 : Missing Numbers

Easy
0/40
Average time to solve is 28m
20 upvotes
Asked in companies
GoogleAdobeOla

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4
1 2 4 6
3
1 2 3
Sample Output 1:
3 5
[Blank]
Explanation for Sample Output 1:
In test case 1, As only 3 and 5 are not in the array and both lie in the range of the array. Thus answer would be "3 5" i.e sorted order.

In test case 2, Since all the elements are present from 1 to 3, the empty list is returned as a answer.
Sample Input 2:
2
3
7 4 9
4
3 6 7 4
Sample Output 2:
3 5 6 8
5
Explanation for Sample Output 2:
In test case 1, As only 3, 5, 6 and 8 are not in the array and lie in the range of the array. Thus answer would be "3 5 6 8" i.e sorted order.

In test case 2, As only 5 is not in the array and lie in the range of the array. Thus answer would be "5".
Hint

Think of searching all the numbers between the maximum element and the minimum element present in the array.

Approaches (3)
Brute Force

The steps are as follows:

 

  1. Get the minimum and maximum elements of the array.
  2. Initialise a list of data type integers, which will store all the missing numbers between the minimum and maximum elements.
  3. For every element between the minimum and maximum number, check whether it is present in the array or not by using linear search.
  4. If it is present, then continue, otherwise add the number in the list.
  5. Finally, return the list.
Time Complexity

O(MAX * N), Where ‘N’ is the length of the array and ‘MAX’ is the maximum element of the array.

 

Since we will be searching for each number between the minimum and maximum element that will take O(MAX) time. Thus total time complexity will be O(N * Max).

Space Complexity

O(1).

 

Since we are using constant extra space. Thus the space complexity will be O(1).

Code Solution
(100% EXP penalty)
Day 19 : Missing Numbers
Full screen
Console