Last Updated: 9 Feb, 2021
Cooking Ninjas
Moderate
Asked in company
In Ninja Land, there is a famous restaurant named ‘CookingNinjas’. There are ‘N’ cooks in ‘CookingNinjas’ numbered from 0 to N-1. Each cook has rank ‘R’ (1 <= R <= 10).
A cook with a rank ‘R’ can prepare 1 dish in the first ‘R’ minutes, 1 more dish in the next ‘2R’ minutes, 1 more dish in next ‘3R’ minutes, and so on (A cook can only make complete dishes) For example if a cook is ranked 2. He will prepare one dish in 2 minutes, one more dish in the next 4 mins and one more in the next 6 minutes hence in a total of 12 minutes he can make 3 dishes, Note, In 13 minutes also he can make only 3 dishes as he does not have enough time for the 4th dish).
One day ‘CookingNinjas’ receive an order of ‘M’ dishes that they need to complete as early as possible. You are given an integer array ‘rank’ of size ‘N’ in which ‘rank[i]’ gives ‘rank’ of ith cook and an integer ‘M’, You need to find out the minimum times required to complete this order of ’M’ dishes.
Note
One dish can be prepared by only one cook, however, two or more cooks can simultaneously prepare different dishes.
For Example
Let ‘N’ = 4, ‘ranks’ = [1, 2, 3, 4] and ‘M’ = 11. Then the minimum time required to cook 11 dishes will be 12 minutes. The cooks should prepare dishes in the following manner -:
Cook-0 prepare 4 dishes in 10 minutes i.e (1 dish in 1 minute, 1 more dish in next 2 minutes, 1 more dish in next 3 minutes, 1 more dish in next 4 minutes).
Cook-1 prepare 3 dishes in 12 minutes i.e (1 dish in 2 minutes, 1 more dish in 4 minutes, 1 more dish in 6 minutes).
Cook-2 prepare 2 dishes in 9 minutes i.e (1 dish in 3 minutes, 1 more dish in the next 6 minutes).
Cook-3 prepare 2 dishes in 12 minutes i.e (1 dish in 4 minutes, 1 more dish in the next 8 minutes).
If all four cooks work simultaneously then they can prepare(4 + 3 + 2 + 2 = 11) dishes in 12 minutes. And it is the minimum possible time.
Input Format
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next 2*T lines represent the ‘T’ test cases.
The first line of each test case contains two space-separated integers ‘N’ and ‘M’ representing the number of cooks and dishes respectively.
The second line of the test case contains ‘N’ space-separated integers representing ‘ranks’ of cooks
Output Format
For each test case, print a line consisting of a single integer that represents the minimum times required to complete the order of ’M’ dishes.
Note
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints
1 <= T <= 50
1 <= N <= 20
1 <= M <= 10^4
1 <= rank[i] <= 10
Time Limit: 1 sec
Approaches
For each time duration starting from one, we count how many dishes each of the cooks can make, If at any duration the total number of dishes is more or equal to ‘M’ then this duration will be the minimum time required to cook ‘M’ dishes.
Algorithm
- Initialize an integer variable ‘duration’ := 1, and declare an integer variable ‘minTime’
- Run a while loop till we don’t find the duration in which cooks can complete the order. In each iteration of the loop, we do the following.
- Initialize an integer variable ‘dishCooked’: = 0.
- Run a loop where ‘i’ ranges from 0 to N-1, and for ith chef do following-:
- Initialize integer variables ‘timeRemain’ : = ‘duration’ and ‘dishCount’ := ‘0’.
- Run a while loop till ‘timeRemain’ > 0 and in each iteration decrement ‘timeRemain’ by (‘dishCount’ + 1) * rank[i], if ‘timeRemain’ >= 0, increment dishCount by ‘1’.
- Increment ‘dishCooked’ by ‘dishCount’.
- If ‘dishCooked’ >= M, then assign ‘minTIme’:= duration and break the loop
- Else, increment duration by 1 and repeat the process.
- Return ‘minTime’.
Let ‘T’ time is required for a cook having rank ‘R’ to prepare ‘K’ dishes then
T = (R*(K * (K+1)))/2.
It implies, K^2 + K - 2*T/R = 0
Or K = (-1 + sqrt(1 + (8*T)/R))/2 (Solution of quadratic equation)
i.e A cook with rank ‘R’ can prepare floor of (-1 + sqrt(1 + (8*T)/R))/2 dishes in ‘T’ times.
We can use this to optimize approach-1 as follows.
Algorithm
- Initialize and integer variable ‘duration’ := 1, and declare an integer variable ‘minTime’
- Run a while loop till we don’t find the duration in which cooks can complete the order. In each iteration of the loop, we do the following.
- Initialize an integer variable ‘dishCooked’: = 0.
- Run a loop where ‘i’ ranges from 0 to N-1, and for each’ increment dishCooked by (-1 + sqrt(1 + (8*duration)/rank[i]))/2.
- If ‘dishCooked’ >= M, then assign ‘minTIme’:= duration and break the loop
- Increment duration by 1.
- Return ‘minTime’.
We can observe that if ‘M’ dishes cannot be prepared in ‘T’ times then they also cannot be prepared at any time between 1 to ‘T’. This suggests that we can apply binary search in time-space. We can also notice, that answer will be between 1 and 10*(M*(M+1))/2 where 10 is the maximum value of rank and ‘M’ is the number of dishes to prepare.
Algorithm
- Initialize low = 1, high = 5*(M*(M+1)).
- While high > low:
- Assign mid := (high + low)/2.
- Initialize an integer variable ‘dishCooked’: = 0.
- Run a loop where ‘i’ ranges from 0 to N-1, and for each ‘i’ increment dishCooked by (-1 + sqrt(1 + (8*mid)/rank[i]))/2. .
- If ‘dishCooked’ < ‘M’, then assign ‘low’ := ‘mid’ + 1.
- Otherwise, Assign ‘high’:= ‘mid’.
- Return ‘high’.
Similar problems
Pair Product Div by K
Moderate
Posted: 15 May, 2022
Pair Product Div by K
Moderate
Posted: 15 May, 2022
Merge Two Sorted Arrays Without Extra Space
Moderate
Posted: 19 Nov, 2022
Merge Two Sorted Arrays Without Extra Space
Moderate
Posted: 19 Nov, 2022
Co-Prime
Hard
Posted: 14 Dec, 2022
First Digit One
Moderate
Posted: 14 Oct, 2025
Special Digit Numbers
Hard
Posted: 31 Oct, 2025