Anish and MEX!

Easy
0/40
Average time to solve is 20m
profile
Contributed by
2 upvotes
Asked in companies
OracleTCS

Problem statement

The WT20 has started and Anish is busy watching it. However, he also has to complete his maths homework. His maths teacher has given him an array and asked him to reorder the array in such a way that the following is satisfied.

Let B1 be the MEX of the elements [ARR1].

Let B2 be the MEX of the elements [ARR1, ARR2].

Let Bn be the MEX of the elements [ARR1, ARR2, ………………………….. ARRn ].

The sum of B2 + B2 ………………. Bn is maximum.

Note:- MEX of an array is the smallest non-negative element missing in the array. Example MEX of [0, 1, 3, 4] is 2.

Example:- 
Let, 

N = 4
ARR = [2, 1, 0, 3]

Answer:- 10 (1 + 2 + 3 + 4) (The re-ordered array is [0, 1, 2, 3], so the MEXs will be 1, 2, 3, and 4).

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of each test case contains an integer ‘N’ denoting the length of the array given.

The next line of every test case contains ‘N’ integers containing the elements of the array arr.
Output Format : 
For each test case, print an integer denoting the maximum sum possible.

The output of each test case should be printed in a separate line.
Note : 
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 5
1 <= N <= 10^5
1 <= ARR[i] <= 10^9  

Time Limit: 1 sec
Sample Input 1 :
2
3 
0 3 3
4 
10 2 3 4
Sample Output 1 :
3
0
Explanation for Sample Output 1 :
In the first test case, the answer should be 2 because you can re-arrange the array as [1, 3, 3] so the MEXs will be 1, 1, and 1 which sums up to 3.
In the second test case, the answer should be 0 because no matter how you re-arrange the elements the MEX will always be 0 as 0 is not present in the array.
Sample Input 2 :
1
4
0 1 6 7
Sample Output 2 :
7
Hint

First try to put all the unique elements in the array.

Approaches (1)
Greedy

We can observe that it is always optimal to put a unique element rather than a repeated element because a repeated element does not increase the MEX of an array. So we will first put the unique elements of the array in ascending order first, then we will put the rest of the elements. 

 

Algorithm:-

 

  1. Initialize a map or dictionary named COUNT to store the frequency of the elements.
  2. Create a set with the elements of the array ARR and sort it (let the name of the set be S).
  3. Iterate over the array ARR. (Let the name of the iterator be i).
    1. Increment COUNT[i] by 1.
  4. Iterate over the dictionary COUNT. (Let the iterator be i).
    1. Iterate from 0 to COUNT[i]. (Let the iterator be j).
      1. Append i to the end of S.
  5. Initialize a variable named K with 0 to store the current MEX.
  6. Initialize a variable named ANS with 0 to store the sum of all the MEXs.
  7. Iterate from 0 to length of S.
    1. If S[i] is equal to K, increment K by 1.
    2. Increment ANS by K.
  8. Return ANS.
Time Complexity

O(N log N), where N is the length of the array.

We are iterating over the array once after sorting, so the time complexity is O(N log N).

Space Complexity

O(N),

We are using a map or dictionary to store the count of elements in the array, so the space complexity is O(N).

Code Solution
(100% EXP penalty)
Anish and MEX!
Full screen
Console