Minimum time required Solution

This is one of the medium difficulty problems in the search section of Hackerrank’s interview preparation kit problem set. Link here.

The problem states that we are given an array of n production rates of machines. The rates express how many days it takes a machine to produce a single unit of some item. The data machines={1,3} means that you have two machines one produces one every day and the other one produces 1 every 3 days. Now given a production goal, you need to find the minimum number of days it takes all your machines to achieve that goal.

Solution

The brute force solution to this problem is to decrease the goal every day a machine produces an item and count the days it takes to get to zero. It makes our submission time out and we can do much better.

One key observation is that we don’t need to compute the the production of our machines at every day. Given any day, we can compute the production in linear time. Now consider the worst case scenario our slowest machine produces all the units by itself call it max_days. One obvious fact is that the minimum number of days to achieve the goal is between 1 and max_days.

If you are familiar with binary search you may know where this is going. The number of days is non-decreasing so we can use binary search to look within the range of possible days one where we produce no less than the required production goal.

UPDATE:

After further thinking max_days does not need to be the slowest machine. Since one machine only is the worst case a tighter upper search bound is the fastest machine. There is also a better lowerbound fastest_machine*goal/number_of_machines This comes from the fact that our production goal will not exceed actual production at the day fo our goal

Solution

link to code on github

long compute_rec(vector<long> machines, long p_goal, long min_days, long max_days){
    if(machines.size()==1)
        return max_days;
    
    if(min_days == max_days)
        return min_days;
    
    long mid = ( min_days + max_days )/2;
    long production = 0;
    
    for(int i =0; i< machines.size();i++)
        production+=floor(mid/machines[i]);
    
    if(production >= p_goal)
        return compute_time_rec(machines,p_goal, min_days, mid);
    else
        return compute_time_rec(machines, p_goal, mid+1, max_days);
}
long minTime(vector<long> machines, long goal) {
    
    sort(machines.begin(), machines.end());
    return compute_rec(machines, goal, 1, machines.back()*goal);
    
}

Bonus

Wow a bonus solution! If you dislike recursion here is a bonus iterative solution. Just call it with the same params as the recursive solution. A better formatted version is in the same github links as above.

long compute_time_iter(vector<long> machines, long production_goal, long min_days, long max_days){
    if(machines.size()==1) return max_days;
    
    long mid;
    long production;
    
    while(min_days != max_days){
        mid = ( min_days + max_days )/2;
        production = 0;
        for(int i =0; i< machines.size();i++)
            production+=floor(mid/machines[i]);
        if(production >= production_goal)
            max_days = mid;
        else
            min_days = mid+1;
    }
    
    return min_days;
}