Homework answers / question archive / Letty is hired as a Sales Executive and her role is to sell items which are given to her in a bag

Letty is hired as a Sales Executive and her role is to sell items which are given to her in a bag

Computer Science

Share With

Letty is hired as a Sales Executive and her role is to sell items which are given to her in a bag. The bag contains n items where each item has an associated ID. Letty is inherently lazy and plans to delete a few items from her bag, but if she deletes more than m items, her mischief will be easily discovered. She also knows that selling like items makes her task simpler, so she wants her bag to contain as few different IDs as possible. Determine the minimum number of different IDs the final bag can contain if she can perform at most m deletions.
For example, she has a bag with n = 6 items, ids = [1, 1, 1, 2, 3, 2], and the maximum number of items she can delete is m = 2. Two possible actions are delete two items with ID = 2 or one with ID = 2 and one with ID = 3. Either way she will have 2 item IDs in the final bag: either ids = [1, 1, 1, 3] or ids = [1, 1, 1, 2].
Function Description
Complete the function deleteProducts in the editor below. The function must return an integer that represents the minimum number of item IDs in her bag after at most m deletions.deleteProducts has the following parameters:
 ids[ids[0],...ids[n-1]]: an array of integers
 m: an integer
Constraints
1 ≤ n ≤ 100000
1 ≤ ids[i] ≤ 1000000
1 ≤ m ≤ 10000
 Input Format For Custom Testing
The first line contains an integer, n, that denotes the number of elements in ids.
Each line i of the n subsequent lines (where 0 ≤ i < n) contains an integer that describes ids[i].
The next line contains an integer, m, that denotes the maximum number of items that can be deleted.
Sample Case 0
Sample Input For Custom Testing
4
1
1
1
1
2
Sample Output
1
Explanation
The bag contains 4 items of the same kind. Whichever item Letty deletes, she will have items of only ID = 1.
Sample Case 1

Sample Input For Custom Testing


6
1
2
3
1
2
2
3
Sample Output


1
Explanation


At most m = 3 items can be deleted from ids = [1, 2, 3, 1, 2, 2]. It is optimal to choose the items having IDs 1 or 3, leaving 3 items with ID = 2.