Minimum Time Required - Hacker Rank 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 consist 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 .

Minimum Time Required - Hacker Rank Solution

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

So, we can iterate over all the days starting from  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 , which will not pass as number of days can be as larges as . 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).

Problem Setter's code:

#include<bits/stdc++.h>
using namespace std;

int main()
{
 int n;
 long long goal,ans;
 scanf("%d%lld",&n,&goal);
 long long machines[n];
 for(int i=0;i<n;i++)
 {
  scanf("%lld",&machines[i]);
 }
 long long low=1;
 long long high=1e18;
 while(low<=high)
 {
  long long mid=(low+high)/2;
  long long done=0;
  for(int i=0;i<n;i++) 
  {
   done+=mid/machines[i];
   if(done>=goal)
    break;
  }
  if(done>=goal)
  {
   high=mid-1;
   ans=mid;
  }
  else
   low=mid+1;
 }
 printf("%lld\n",ans);
 return 0;
}