Last Updated: 20 Oct, 2021

Anish and MEX!

Easy

Asked in companies

Solve now

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

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

Solve now

Approaches

01 Approach

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

Initialize a map or dictionary named COUNT to store the frequency of the elements.
Create a set with the elements of the array ARR and sort it (let the name of the set be S).
Iterate over the array ARR. (Let the name of the iterator be i).
1. Increment COUNT[i] by 1.
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.
Initialize a variable named K with 0 to store the current MEX.
Initialize a variable named ANS with 0 to store the sum of all the MEXs.
Iterate from 0 to length of S.
1. If S[i] is equal to K, increment K by 1.
2. Increment ANS by K.
Return ANS.

Solve now