0

Minimum Distinct Labels

Difficulty: MEDIUM
Avg. time to solve
15 min
Success Rate
85%

Problem Statement
Suggest Edit

'N' boxes are placed on a table. Each box has an integer label on it. The labels present on each box are given in the array 'ARR'. Two different boxes may or may not have the same label value. You are given an integer 'M'. Your task is to remove any 'M' of the 'N' boxes such that after their removal, the number of distinct labels left on the table are minimum.

For example:

Consider M = 2 and the array ARR = [ 3, 4, 5, 3 ] 
If we remove the second and the third box, then all the boxes remaining on the table will have label 3. Hence, the minimum number of distinct labels left will be 1 in this case.
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, 'N' and 'M', denoting the number of boxes and the number of boxes to be removed respectively.

The second line of each test case contains 'N' space-separated integers denoting the labels of each box.
Output Format:
For each test case, return the minimum number of distinct labels left on the table after removing exactly 'M' boxes.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^4 
0 <= M <= N
1 <= ARR[i] <= 10^9

Time Limit: 1 sec
Sample Input 1:
2
4 3
1 2 2 3
3 1
1 2 2
Sample Output 1:
1
1
Explanation for Sample Input 1:
For the first test case : 
If we remove the first 3 boxes, then only one box having label 3 will be left on the table. Hence, the minimum number of distinct labels will be 1 in this case. Note that removing any 3 of the 4 boxes produces the same result.

For the second test case : 
If we remove the first box, then all the boxes left on the table will have label 2. Hence, the minimum number of distinct labels will be 1 in this case.
Sample Input 2:
2
4 1
3 3 2 5
4 0
1 2 1 3
Sample Output 2:
2
3
Reset Code
Full screen
copy-code
Console