Last Updated: 10 Sep, 2021
Minimum Dishes to Cook
Moderate
Asked in company
The chef has received the order to make ‘N’ dishes represented by an array ‘Arr’, where ‘Arr[i]’ denotes the type of dish.
Chef has the liberty to cancel at most ‘M’ orders. He cancels the order in such a way that the different types of dishes he has to cook are minimized. The chef is lazy and dumb so he has asked you to help him.
Find the count of the minimum variety of dishes that the chef will have to cook.
For Example :
If N = 6, Arr = { 1, 2, 3, 1, 1, 2 } and M = 2
Then the chef will have to cook at least 2 different varieties of dishes, because:
He may cancel the orders for both the dishes of type 2, now he left with {1, 1, 1, 3}
He may cancel the orders for dish type 3 and one of the orders of dish type 1, now he left with {2, 1, 1, 2}
There are many other ways to cancel the orders, but none of them will result in an answer less than 2, hence we will return the value 2.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains two integers ‘N’ and ‘M’, denoting the number of orders and the maximum number of orders the chef can cancel respectively.
The next line contains N integers, ‘Arr[i]’ denoting the type of the i<sup>th</sup> dish.
Output Format :
For each test case, print a single integer denoting the minimum types of dishes that the chef will have to cook.
Output for each test case will 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 <= 10
0 <= M < N <= 500
0 <= Arr[i] <= 1’000’000’000
Time limit: 1 sec
Approaches
Create a hash-map to store how many times a particular dish is ordered. Now Iterate this hash-map and each time remove the dish with the least frequency if the current cancellations allowed are greater than or equal to the least frequency, also deduct the least frequency from the current cancellations allowed. Keep repeating this till the point when the least frequency is less than or equal to current cancellations allowed.
Finally return the size of the hash-map, as this will be the minimum variety of dishes the Chef will have to cook.
The steps are as follows :
- Initialize a hash-map “mp” to store the frequency of each dish, now fill in the hash-map.
- Run a while loop, find the dish with the least frequency in the hash-map, let the frequency of that dish be “freq”. If freq <= M, then deduct the value of “freq” from ‘M’ and also delete the dish with the least frequency.
- Break the while loop if freq > M.
- Finally, return the size of “mp” as this will be the minimum dishes the chef will have to cook.
Create a hash-map to store how many times a particular dish is ordered. Now make a new array storing only the frequencies of all the various dishes, then sort this array.
We can now simply greedily find the size of the largest prefix with a sum less than equal to ‘M’. All the dishes corresponding to the frequencies of this prefix will be cancelled, and the remaining array element will denote the frequency of dishes the chef will have to cook, so we can simply return the size of the array remaining after removing the largest prefix array.
The steps are as follows :
- Initialize a hash-map “mp” to store the frequency of each dish, now fill in the hash-map.
- Create a “freqArr” array to store the frequencies of all the different types of dishes. Now sort this array.
- Initialize “totalDish” equal to the size of “freqArr”.
- Initialize “cancelledDish” equal to 0, this variable will store the maximum dishes we can cancel. And its value will be equal to the size of the largest prefix array with a sum less than equal to ‘M’.
- Finally, return the value totalDish - cancelledDish.