Efficient Production

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in company
Amazon

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
1 10
5 
2 3
1 2

Sample Output 1 :

50
2
Explanation Of sample input 1 :
In the first test case:
There is only one machine and it takes 5 units of time to produce one product. So, to produce 50 units it will take 50 units of time.

In the second test case:
After the first unit of time, the first machine will produce one product, total products = 1.
By the second unit of time, the first machine has produced 2 products and the second machine has produced 1 product. So, total products = 3 = 'K'.

Sample Input 2 :

2
6 7
11 11 11 11 11 11
5 5
1 1 1 1 1

Sample Output 2 :

22 
1
Hint

Can we iterate on time from 1 to 10 ^ 18 and check the number of products produced till this time?

Approaches (2)
Brute Force

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:

 

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

O(N * M ), where ‘N’ is the number of machines and M is 10 ^ 18.

 

For each value of ‘time’, we iterate over all the machines and calculate products produced by them so, the overall time complexity will be  O(N * M).

Space Complexity

O(1). 

 

Constant space required.

Code Solution
(100% EXP penalty)
Efficient Production
Full screen
Console