HackerRank ‘Minimum Time Required’ Solution

Short Problem Definition:

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.

Link

Minimum Time Required

Complexity:

time complexity is O(N*log(10*9))

space complexity is O(1)

Execution:

This problem statement is a typical binary search challenge. It has a function (the sum of production) that changes in relation to some linear variable (time).

The bounds can be limited by the minimal and maximal production of each machine in the array. This means that the range is 1-10*9, but for most cases, it will be more constrained. It is a big number, but if the function is fast enough, it can be solved in a reasonable time.

There are 10*5 machines, there are completely independent and we have to visit all of them for each iteration. There is no point in memoizing or preprocessing any values, since they change with every iteration.

Hence the time complexity is O(N * log(10*9)).

P.S I always take forever to get binary search right. I should keep a templated (lambda) version of it available, for problems such as this one.

Solution:
#!/bin/python

import math
import os
import random
import re
import sys

# Complete the minTime function below.
def minTime(machines, goal):
    low_bound = goal * min(machines) // len(machines)
    high_bound = goal * max(machines) // len(machines) + 1

    while low_bound < high_bound:
        days = (low_bound+high_bound) // 2
        produced = sum([days // machine for machine in machines])
        if produced >= goal:
            high_bound = days
        else:
            low_bound = days + 1
    
    return low_bound

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nGoal = raw_input().split()

    n = int(nGoal[0])

    goal = int(nGoal[1])

    machines = map(long, raw_input().rstrip().split())

    ans = minTime(machines, goal)

    fptr.write(str(ans) + '\n')

    fptr.close()


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin