Chefs and Dishes

Easy
0/40
Average time to solve is 30m
profile
Contributed by
1 upvote

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3 7
3 4 5
3 4
2 1 2
Sample Output 1 :
10
2
Explanation of Sample 1 :
For test case 1:
At time = 0, there will be 0 dishes prepared.
At time = 3, chef 0 will complete a dish so there will be 1 dish in total.
At time = 4, chef 1 will complete a dish so there will be 2 dishes in total.
At time = 5, chef 2 will complete a dish so there will be 3 dishes in total.
At time = 6, chef 0 will complete a dish so there will be 4 dishes in total.
At time = 8, chef 1 will complete a dish so there will be 5 dishes in total.
At time = 9, chef 0 will complete a dish so there will be 6 dishes in total.
At time = 10, chef 2 will complete a dish so there will be 7 dishes in total.   
Hence, 10 minutes are required to complete 7 dishes.

For test case 2:
At time = 0, there will be 0 dishes prepared.
At time = 1, chef 1 will complete a dish so there will be 1 dish in total.
At time = 2, chef 0, chef 1 and chef 2 will complete a dish each so there will be 4 dishes in total.
Hence, 2 minutes are required to complete 4 dishes.
Sample Input 2 :
2
4 7
1 4 3 5
4 5
7 9 2 10
Sample Output 2 :
5
8
Hint

We can add up the contributions of each chef to calculate how many dishes have been made when a certain time has elapsed.

Approaches (1)
Binary Search

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

O(N * log(M * MAX)), where 'N' is the number of chefs, 'M' the number of dishes to make, and 'MAX' is the value of the maximum element in 'A'.

 

We are using binary search with bounds 1 and 'M * MAX' which runs in logarithmic time, so the time complexity is O(log(M * MAX)). And for each iteration of binary search, we are iterating through the array of length 'N'.  So, the total time complexity is O(N * log(M * MAX)).

Space Complexity

O(1).

 

We are only using constant extra space. So, the space complexity is O(1).

Code Solution
(100% EXP penalty)
Chefs and Dishes
Full screen
Console