Last Updated: 31 Jul, 2022

Chefs and Dishes

Easy

Problem statement

In a restaurant, there are 'N' chefs numbered from 0 to 'N - 1'. It takes the 'i'th chef 'A[i]' minutes to make one dish.

All the chefs start to make the dishes at the exact same time. Your task is to return the minimum time required to make at least 'M' dishes in total.

For example :

Let's say 'N' = 2, 'M' = 5, 'A' = {2, 3}
At time = 0, there will be 0 dishes prepared.
At time = 2, chef 0 will complete a dish so there will be 1 dish in total.
At time = 3, chef 1 will complete a dish so there will be 2 dishes in total.
At time = 4, chef 0 will complete a dish so there will be 3 dishes in total.
At time = 6, chef 0 and 1 will both complete a dish so there will be 5 dishes in total.
Hence, 6 minutes are required to complete 5 dishes.

Input Format :

The first line of input contains a single integer 'T', which denotes the number of test cases.

Then 'T' test cases follow. For each test case:

The first line contains two space-separated integers 'N' and 'M', denoting the number of chefs and the number of dishes to make, respectively.

The second line contains 'N' space-separated integers, representing the values of the array 'A'.

Output Format :

For each test case, you must return the minimum time required to make at least 'M' dishes in total

Note :

You don't need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^5
1 <= M <= 10^9
1 <= A[i] <= 10^5   

The sum of 'N' over all test cases does not exceed 10^5.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach :

Let us first define a function 'F(T)' which tells whether at least 'M' dishes can be made when 'T' time has elapsed. This function will be false for some initial values of 'T' in which 'M' dishes cannot be made. Then after a certain value, the function will be true for that and all greater values of 'T'.
So, we just have to find the minimum value of 'T' for which 'F(T)' is true. We can do that using binary search.
The lower bound of binary search will be 1 and for the upper bound we use the maximum possible value of the answer, which can be 'M * maximumElement'.
For checking how many dishes will be made in time 'T', we iterate through the times of the 'N' chefs and add up each chef's contribution which will be 'T / A[i]'.

Algorithm :

Declare a variable 'N' as the length of the array 'A', denoting the number of chefs.
Declare a variable 'mx' and store the maximum element present in the array 'A'.
Declare variables 'l = 1' and 'r = M * mx' as the bounds for binary search and 'ans' for storing the answer.
Run a while loop with condition 'l <= r'.
- Declare a variable 'mid = (l + r) / 2' denoting the time elapsed.
- Declare a variable 'dishes' for storing the number of dishes made when 'mid' time has elapsed.
- Iterate over the array 'A' and in each iteration, add 'i'th chefs contribution 'mid / A[i]' to 'dishes'.
- Assign 'l' with value 'mid + 1' if 'dishes < M'; otherwise, assign 'ans' with value 'mid' and 'r' with value 'mid - 1'.
Return 'ans'.

Solve now