Last Updated: 24 Apr, 2021

Efficient Production

Easy

Asked in company

Solve now

Problem statement

Kevin has started a new production line. He has ‘N’ machines that can work simultaneously. All machines produce the same product but at a different speed. Time taken to produce one product by machines is given as an array ‘ARR’.

Kevin is new in the production business and so, he wants your help in producing ‘K’ products in the minimum possible time.

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases. The 'T' test cases follow.

The first line of each test case will contain two space-separated integers ‘N’, and ‘K’ which denotes the number of machines and the total number of products, respectively.

The next line contains the ‘N’ space-separated integers, where ‘i-th’ element denotes the time taken by ‘i-th’ machine to produce one product.

Output Format :

For each test case, print an integer denoting the minimum time required to produce ‘K’ products. 

Output for every test case will be printed in a separate line.

Note :

You do not need to print anything; It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 100000
1 <= K, ARR[i] <= 10^9

Where 'ARR[i]' denotes the 'ith' element of ARR.

Time limit: 1 sec

Solve now

Approaches

01 Approach

We will iterate over the time from 1 to 10 ^ 18 and check the number of products produced till this time. For, given constraints, 10 ^ 18 is the maximum time machines will take to produce ‘K’ products.

To calculate the number of products produced we will go through all the machines and add the products produced by this machine.

The steps are as follows:

Iterate from 1 to 10 ^ 18. (say, iterator = 'i')
1. Create a variable ‘products’ to keep count of products produced.
2. Iterate from 0 to ‘N’-1. (say, iterator = 'j')
  1. ‘products’ += ‘i’ / ‘arr[ j ]’
3. If ‘products’ >= ‘K’
  1. return ‘i’

Solve now

02 Approach

We will use binary search to find the required time efficiently. We will initialize the range of time from 1 to 10 ^ 18. For the given constraints, 10 ^ 18 is the maximum time machines will take to produce ‘K’ products.

For each range of time, we will find its middle value and calculate the number of products produced till the middle.

To calculate the number of products produced we will go through all the machines and add the products produced by this machine till the middle. Depending on the value of products produced, update the range of time.

The steps are as follows:

Create a variable ‘ans’ to store the final answer.
Create a variable ‘left’ initialized to 1,to store the left limit of our binary search.
Create a variable ‘right’ initialized to 10 ^ 18, to store the right limit of our binary search.
Iterate until 'left' becomes greater than 'right'
1. Create a variable ‘middle’ to store the middle of ‘left’ and ‘right’
2. Compute the middle of ‘left’ and ‘right’ and store into the ‘middle’.
3. Create a variable ‘products’ to store the products produced till ‘middle’
4. Iterate from 0 to ‘N’-1. (say, iterator = 'i')
  1. ‘products’ += ‘middle’/ ‘arr[i]’
5. If ‘products’ < ‘K’
  1. We can't not produce ‘k’ items till middle so increase the ‘left’ limit
  2. ‘left’ = ‘middle’ + 1
6. Else
  1. ‘ans’ = ’middle’
  2. ‘right’ = ‘middle’
Return ‘ans’

Solve now