Minimum Distinct Labels

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in companies
Expedia GroupMorgan Stanley

Problem statement

'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.
Detailed explanation ( Input/output format, Notes, Images )
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
Hint

Generate all the possible combinations of M boxes that can be removed, and check the number of distinct labels left for each combination.

Approaches (2)
Brute Force Approach

The idea is to generate all the possible combinations of the ‘M’ boxes that can be removed, and for each combination, find out the number of distinct labels that are left on the table and compare it with results obtained from all other combinations. In the end we will return minimum possible labels obtained.

To check the number of distinct labels left, we will insert all the labels on the boxes which are not removed into a set and the number of distinct labels will be equal to the number of elements in the set. 

To generate all the combinations of removals, we will take help of the next permutation function. We will create an array having ‘M’ zeros and ‘N’ - ‘M’ ones to store the current combination. The ‘M’ zeros will represent the indices of the boxes that will be removed, and the ‘N’ - ‘M’ ones will represent the indices of the boxes left on the table. We will place all the ‘M’ zeros at the start of the array and the ones at the end. To move to the next combination we will call the next permutation function for the current permutation.

 

Steps:

  1. Let 'ANS' be the minimum distinct labels left. Initialize it as the number of distinct labels initially present on the table.
  2. Create an array 'PERM' having ‘M’ zeros followed by ‘N’ - ‘M’ ones to store the current permutation.
  3. While a greater permutation for the current permutation exists,
    • Change current permutation to the next permutation.
    • Create an empty set ‘LABS’ to store the distinct labels.
    • Iterate from ‘j’ = 0 to ‘N - 1’
      • If 'PERM'[j] is equal to 1, then insert ARR[i] to the set ‘LABELS’. 
    • Let the number of elements in the set ‘LABELS’ be ‘K’
    • Set 'ANS' to the minimum value among 'ANS' and ‘K’. 
  4. Return the variable 'ANS'.
Time Complexity

O(N * C(N,M)), where ‘N’ is the number of boxes, ‘M’ is the number of boxes to be removed, and ‘C’ denotes the Binomial Coefficient.

 

There are C(N,M) possible combinations of the ‘M’ boxes that can be removed, and it takes O(N) time to find the number of distinct labels for each combination. Hence, the overall Time Complexity is O(N*C(N,M)).

Space Complexity

O(N), where ‘N’ denotes the number of boxes.

 

The number of elements in the perm array is ‘N’. Hence, the overall Space Complexity is O(N).

Code Solution
(100% EXP penalty)
Minimum Distinct Labels
Full screen
Console