## 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^{18} 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^{18}. 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.