Minimum Dishes to Cook

Moderate
0/80
profile
Contributed by
2 upvotes
Asked in company
Adobe

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
6 2
1 2 3 1 1 2
4 2
1 1 1 1
Sample Output 1 :
2
1
Explanation For Sample Input 1 :
For test case 1 : 
We will return 2, because:
The chef will cancel the orders for both the dishes of type 2, now he left with {1, 1, 1, 3}

For test case 2 : 
We will return 1, because:
Regardless of whether the chef cancels the order or not, we will have to cook at least 1 dish in this case.
Sample Input 2 :
2
5 4
1 2 3 4 5
5 3
1 2 3 4 5
Sample Output 2 :
1
2
Hint

The Chef will greedily try to cancel the orders which have the dishes with the least frequency.

Approaches (2)
Greedy Approach

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.
Time Complexity

O( N ^ 2 ), where N denotes the number of orders


In the worst case when all the ‘N’ orders are for different dishes and the chef can cancel ‘N-1’ dishes, then we will be removing one dish at a time after traversing all the remaining dishes. 

Hence the time complexity is O( N^2 ).

Space Complexity

O( N ), where N denotes the number of orders

 

In the worst case when all the ‘N’ orders are for different dishes we will build a hash-map of size ~N.

Hence the space complexity is O( N )

Code Solution
(100% EXP penalty)
Minimum Dishes to Cook
Full screen
Console