Hackerrank - Minimum Time Required Solution

You are planning production for an order. You have a number of machines that each have a fixed number of days to produce an item. Given that all the machines operate simultaneously, determine the minimum number of days to produce the required order.

For example, you have to produce  items. You have three machines that take  days to produce an item. The following is a schedule of items produced:

Day Production  Count
2   2               2
3   1               3
4   2               5
6   3               8
8   2              10

It takes  days to produce  items using these machines.

Function Description

Complete the minimumTime function in the editor below. It should return an integer representing the minimum number of days required to complete the order.

minimumTime has the following parameter(s):

• machines: an array of integers representing days to produce one item per machine
• goal: an integer, the number of items required to complete the order

Input Format

The first line consists of two integers  and , the size of  and the target production.
The next line contains  space-separated integers, .

Constraints

Output Format

Return the minimum time required to produce  items considering all machines work simultaneously.

Sample Input 0

2 5
2 3

Sample Output 0

6

Explanation 0

In  days  can produce  items and  can produce  items. This totals up to .

Sample Input 1

3 10
1 3 4

Sample Output 1

7

Explanation 1

In  minutes,  can produce  items,  can produce  items and  can produce  item, which totals up to .

Sample Input 2

3 12
4 5 6

Sample Output 2

20

Explanation 2

In  days  can produce  items,  can produce , and  can produce .

Solution in Python

from math import ceil
from collections import Counter

def minTime(machines, goal):
    c = Counter(machines)
    fastest = min(c)
    min_days = 1
    max_days = ceil((fastest*goal)/c[fastest])
    while max_days-min_days>1:
        mid = (min_days+max_days)//2
        output = sum((mid//x)*y for x,y in c.items())
        if output<goal:
            min_days = mid
        else:
            max_days = mid
    return max_days

n,goal = map(int,input().split())
machines = list(map(int,input().split()))
print(minTime(machines, goal))

Algorithm explanation

We know that since the goal is atleast 1, then we need a minimum of 1 day to complete the task and a maximum of 10¹⁸ days (when goal is 1 and the number of machine is 1 and it's rate is 1).

So, we can iterate over all the days starting from 1 and check for each number of days if our goal can be accomplished by traversing the array and getting the total count of number of items produced in that many number of days. The complexity is this approach will be O(days*n), which will not pass as number of days can be as larges as 10¹⁸. We can do better.

This problem can be solved using binary search over the answer. Since we have the  and  pointers, we can apply binary search. Now, at every iteration we check if we can complete our task in  days by traversing the array and summing up the total items produced by each machine. If yes, then we move towards left else we move towards right (Since, we need to minimize the answer).

Python code explanation

Lets machines = [2,3,2] and goal = 20

First, we group machines that take the same number of days using Counter

>>> c = Counter(machines)
>>> c
Counter({2: 2, 3: 1})

We already know that minimum days it will take to reach our goal is 1 therefore, min_days = 1

Now we have to find the maximum days it will take.

Maximum days will be given by goal*days taken by fastest machine/total count of the fastest machine

Our fastest machine produces 1 unit in 2 days therefore it will take at least 2*goal = 2*20 = 40 days if we use only 1 of our fastest machine.

>>> fastest = min(c)
>>> fastest
2

But since we have 2 counts of our fastest machine we will divide this number by 2

Therefore max_days = 20

>>> max_days = ceil((fastest*goal)/c[fastest])
>>> max_days
20

Now we know that our total number of days will be anywhere between 1 to 20 days

The number of output produced by a machine on a particular day can be obtained by days//number of days to produce 1 unit

Example day = 5, machine speed = 2, i.e 1 unit every 2 days

Total output in day 5 = 5//2 = 2

If we have more than 1 of the same machine, (5//2)*number of machines

For example, on day 5 our fastest machine will product 5//2*2 = 4 units instead of 2 since we have more than one of the same machines.

Therefore we can use the following code to find the total output on a particular day for all machines combined.

>>> sum((day//x)*y for x,y in c.items())

where x is number of days taken by that machine to produce 1 unit and y is the total count of that machine

Now the looping part

while max_days-min_days>1:
    mid = (min_days+max_days)//2
    output = sum((mid//x)*y for x,y in c.items())
    if output<goal:
        min_days = mid
    else:
        max_days = mid

Since we know that it will take anywhere between 1 to 20 days. We will check how many outputs we get in the midpoint that is 20+1//2 = 10th day.

mid = (min_days+max_days)//2 = 10

>>> sum((mid//x)*y for x,y in c.items())
13

Now we know that on the 10th day our total output will be only 13 which means our required answers come after day 10.

Since now we know that it will take atleast 10 day to reach our goal. Therefore we set min_days = min i.e.(min_days = 10)

>>> sum((mid//x)*y for x,y in c.items())
19

Now min_days= 10 and max_days= 20, mid = (10+20)//2 = 15

19 still less than 20 but very close.  Again min_days = min i.e.(min_days = 15)

Now min_days= 15 and max_days= 20, mid = (15+20)//2 = 17

>>> sum((mid//x)*y for x,y in c.items())
21

Since 21 exceeds our goal=20, We now set max_days = mid i.e(max_days = 17)

Now min_days= 15 and max_days= 17, mid = (15+17)//2 = 16

>>> sum((mid//x)*y for x,y in c.items())
21

Since 21 exceeds our goal=20, We now set max_days = mid i.e(max_days = 16)

Now min_days= 15 and max_days= 16, mid = (15+17)//2 = 16

>>> sum((mid//x)*y for x,y in c.items())
21

We stop when max_days-min_days = 1. Our required answer will be max_days i.e. 16.

Since, we have already calculated earlier than we don't reach our goal when days = min_days.

That's it. If you have any confusion leave a comment below.