- Minimum Time Required
- Discussions

# Minimum Time Required

# Minimum Time Required

ayushr2 + 4 comments A great question. In case someone is stuck, think of why this is in the "search" section. Could you efficiently search for the number of days it would take to produce the goal?

*n <= 10^5*is the constraint. Which means that our algorithm can be*O(n logn)*.Given the number of days, it take

*O(n)*to compute the items produced in those days by*n*machines. So we have*log n*searched allowed to find the correct day (where items produced fulfils the goal).Does it ring any bells? Ping me if you still have a question.

divyakumar2707 + 1 comment [deleted]divyakumar2707 + 2 comments [deleted]ayushr2 + 1 comment There are a couple of things. Once you hit count == goal, you have to realise that it might be true that mid - 1 also produces the same result and so does mid - 2. You have to get the minimum out of that. I recommend you have a while loop which keeps reducing mid once you hit count == goal and keep rechecking.

divyakumar2707 + 2 comments [deleted]patil_amit155 + 0 comments Same problem with me... Did you resolve this?

s14_190031845 + 0 comments why u deleted

fynx_gloire + 0 comments Hello, can you please explain this problem to me. I still do not even understand the problem statement.

Thanks in advance

liuyuhao717 + 1 comment Hi. You said " n <= 10^5 is the constraint. Which means that our algorithm can be O(n logn)." .

Can I know Why? Thanks You

aalapshah12297 + 0 comments Usually for competitive coding problems, the time limit is around 1 second and you can safely assume that you can perform 10^8 to 10^9 operations within that time. So when the constraint is given as n <= 10^5, it serves to us as a hint that any O(nlogn) algorithm will suffice. Similarly, n <= 10^4 usually implies quadratic runtime and n <= 10^9 implies that a linear runtime is required. Of course, the constants also come into play, but these serve as a general guidline for most problems.

cris_kgl + 4 comments Hello ayushr2,

I think there is a better solution that runs in O(n) time:

static long minTime(long[] machines, long goal) { double slope = 0; for(long i : machines){//O(N) double temp = (1/(double)i); slope += temp; } double tempSol = goal/slope; if(tempSol/((long)(tempSol)) > 1){//add 1 return (long) tempSol + 1; } return (long) tempSol; }

cris_kgl + 0 comments Only disadvantage of this solution is the rounding problem for numbers that are far too small to be computed with Java primitive types. A possible workaround for this would be using BigDecimal.

miryala + 1 comment can you explain the algorithm please

cris_kgl + 1 comment Sure.

You just have to think about it in terms of machines that I have each day.

**E.g**We have thre machines that take 1,2 and 3 days to deliver 1 product. Consequently:

- machine 1 produces 1 product/day
- machine 2 produces 1/2 product/day
- machine 3 produces 1/3 product/day

Now that the days are our independent variable, we can sum this potential productions with each machine BUILDING A LINEAR EQUATION in the form of:

y = ((1/1)+(1/2)+(1/3))* x ==> y = 0.8333333*x

I recommend you graph that function and a constant function representing the target production. We just need to find in which number they meet. And here

**we have 2 different cases**.- We meet exactly in an integer number of days then we return the correct result

OR

- We meet in a "decimal day" in (e.g 6.2) then we add 1 to get to the next possible integer day.

Hope it helps.

NiakTheWizard + 1 comment Consider the following input:

2 1 2 2

Your approach (slope y = x) would give an answer of 1 day while the correct answer is 2.

cris_kgl + 0 comments you r right. This would work if we could build machines from machines that are being built. in your for example deliver a machine on day 1 would meanbuilding a machine from two half built machines.

thank 4 ur comment.

nevertheless it is important to notice that this approach would beuseful if we are working with uncountable things such as sugar or flour (kg).

have a good day! ;)

adangol1 + 1 comment I understand your logic and tried to implement in python. However, its failing all the test cases except the first three sample cases.

` def minTime(machines, goal): one_daywork = 0 for i in machines: one_daywork += 1/i

`ans = (goal/one_daywork) if (round(ans, 6)).is_integer(): return int(ans) else: return (int(math.ceil(ans))) ````

cris_kgl + 0 comments you r right. This would work if we could build machines from machines that are being built. in your for example deliver a machine on day 1 would meanbuilding a machine from two half built machines. thank 4 ur comment. nevertheless it is important to notice that this approach would beuseful if we are working with uncountable things such as sugar or flour (kg). have a good day! ;)

smwallace1 + 1 comment The problem with this is that you are counting partially-complete production cycles toward your slope. The instantaneous rate of production is correct, but just finding the day that corresponds to the needed production number would lead to problems. For example, at the date that you provide in your answer, two machines could have completed a half of a cycle each, but that would count as a single complete product in this solution. This is a good start, but you need to finalize the method to find what day N complete products are made.

cris_kgl + 0 comments Correct.

Persistencia + 9 comments def minTime(machines, goal): machines.sort() low_rate = machines[0] lower_bound = (goal // (len(machines) / low_rate)) high_rate = machines[-1] upper_bound = (goal // (len(machines) / high_rate)) + 1 while lower_bound < upper_bound: num_days = (lower_bound + upper_bound) // 2 total = getNumItems(machines, goal, num_days) if total >= goal: upper_bound = num_days else: lower_bound = num_days + 1 return int(lower_bound) def getNumItems(machines, goal, num_days): total = 0 for machine in machines: total += (num_days // machine) return total

vishalsingh_mkn + 1 comment I dont get the idea of lower_bound = (goal // (len(machines) / low_rate)). Can you please explain?

Persistencia + 1 comment lower_bound and upper_bound are the lowest and highest rates possible if using the slowest and faster machines, respectively.

vishalsingh_mkn + 2 comments [deleted]vishalsingh_mkn + 0 comments I get it now. Thanks!

Persistencia + 1 comment The numerator is clearly the number of items we want to produce. The denominator represents the number of machines at the given rate. So if we divide the number of items we want with the rate at which we get items, we would get a bound of how many days it would take to reach our goal.

ztytom1 + 1 comment I think this solution is returning wrong answer in case: m = [4,4,4,4] goal = 10

It will return 11 but the correct answer should be 12. My solution also have this problem tho

ztytom1 + 0 comments I think the problem is the setting of lower and upper bound. They should be:

lower_bound = (goal // (len(machines) / low_rate)) + 1

upper_bound = (goal // (len(machines) / high_rate)) + 1

Then the test case m=[4,4,4,4] goal = 10 passes, and also pass all other test cases. But idk if there exist any other test case break the solution

strayapanda + 0 comments wow, nice

tuyanhua_zju + 0 comments Neat. Thank you for help.

sellerdoor + 4 comments No need to sort machines if we only need the min and max values

def minTime(machines, goal): minday = math.ceil(goal / len(machines)) * min(machines) maxday = math.ceil(goal / len(machines) * max(machines)) while minday < maxday: day = (maxday + minday) // 2 if sum(day // m for m in machines) >= goal: maxday = day else: minday = day + 1 return minday

fynx_gloire + 1 comment Hello, can you please explain your logic, I do not quite understand it

thx in advance

eduasinco + 0 comments It is based on the binary search principal, it reduces days in have by each iteration and thus you can run it on nlogn time

kevinolaf + 0 comments Thanks. Here is the JS version of your code

function minTime(m, goal) { const min = Math.min(...m); const max = Math.max(...m); let minDay = Math.ceil(goal / m.length) * min; let maxDay = Math.ceil(goal / m.length) * max; const getSum = (arr, d) => arr.reduce((total, machine) => total + Math.floor(d / machine), 0); while (minDay < maxDay) { const day = Math.floor((maxDay + minDay) / 2); const sum = getSum(m, day); if (sum >= goal) { maxDay = day; } else { minDay = day + 1; } } return minDay; }

meraj_ahmed_ece1 + 1 comment For finding minimum no. of days , should math.floor not be used instead of math.ceil?

tynan_s_daly1 + 0 comments Nope. If I order a package and it takes 2.5 days to arrive I will receive it midway through the 3rd day.

fynx_gloire + 0 comments Hello, can you please explain your logic, I do not quite understand it

thx in advance

taromakino + 1 comment Thanks for the search algorithm. Here are some tighter bounds:

rates = [1 / entry for entry in machines] sum_rate = sum(rates) lb = int(goal / sum_rate) ub = min(machines) * goal

lesanmiguel + 1 comment Are you sure that it is a tighter upper bound? One machine working at the fastest rate vs. all machines working at the slowest rate?

taromakino + 0 comments That would depend on the values in

`machines`

, while the lb will hold regardless.

kt10_truong + 1 comment I'm curious as to why a lower_bound where the integer divison produces a FLOOR result still works?

Let's take the problem's example: if the minRate of a the fastest machine = 2 total of machines = 3 and goal = 10

lower_bound = 2 * (10/3) = 6

Shouldn't it be 7? So then, should this be Integer divsion that rounds up instead of down?

// - by defintion just chops off the decimal right?

hubrando + 0 comments The fact that it is rounded down in the integer divison step means that you overestimate in the later step when you use your while loop.

hubrando + 0 comments So effectively you do a kind of binary search?

yulian_karapetk1 + 2 comments This solution works great in

**Python**but its**JavaScript**equivalent*gives wrong answers in 4 of the tests*. Do you know what the reason might be?function minTime(machines, goal) { machines.sort(); const lowRate = machines[0]; const highRate = machines[machines.length - 1]; let lowerBound = Math.floor(goal / (machines.length / lowRate)); let upperBound = Math.floor(goal / (machines.length / highRate)) + 1; while (lowerBound < upperBound) { const days = Math.floor((lowerBound + upperBound) / 2); const total = getNumItems(machines, days); if (total >= goal) { upperBound = days; } else { lowerBound = days + 1; } } return lowerBound; } function getNumItems(machines, days) { let total = 0; for (const machine of machines) { total += Math.floor(days / machine); } return total; }

uiandgame + 0 comments It may be due to a overflow. To counter that you can put a break in the for loop of getNumItems. It would break when (total >= goal). The rest of the code would remain the same.

diebar_us + 0 comments you should do: machines.sort((a,b) => a-b); instead of just machines.sort() for sorting. otherwise js will do string sort for the values of the array.

kennethjjgibson + 0 comments The first step is identifying that this problem can be solved with search. Given that it's under the search category let's jump straight to the assumption that a search approach will be the best.

When we're performing a search we need to start by defining some bounds (we need to search between two bounds otherwise how do we know where to start/stop)

How do we define our bounds then? Well let's start with the upper bound.

How many days would it take if ALL machines were equally as slow as the slowest machine?

If the slowest machine takes 5 days, we have 3 machines in total, and our goal is 30 then the worst case scenario is tha ALL machines take 5 days.

Given we have 3 machines that means that after 5 days we'll have 3 items produced. That means the worst case is goal / machines * slowestMachine = 50 days.

We can do the same thing to find the lower bound. Let's assume that all 3 machines are as fast as the fastest machine. Our lower bound is then goal / machines * fastestMachine = 10 days.

Now that we have our lower and upper bounds (10 - 50) we can finally start to search.

With binary search we always start at the middle of our bounds. The middle of our bounds is 35 ((lowerBound + upperBound) / 2) so let's start there.

Next we'll try to calculate how many items would be produced after this many days.

For each machine, how many items does it produce after 35 days? For that we use days / machine. Sum each of these values for each machineto get the total number of items produced by all machines after 35 days.

Now we check if we've met our goal or not. If we produce more than our goal, then the half way point that we chose is too high. If we produced less then the half way point was too low.

All we have to do now is repeat the steps but adjust our upper and lower bounds to be (lowerBound - middlePoint) or (middlePoint - upperBound) depending what side of the line we fell.

niet_skc + 1 comment java solution -

static long minTime(long[] machines, long goal) { Arrays.sort(machines); long max = machines[machines.length - 1]; long minDays = 0; long maxDays = max*goal; long result = -1; while (minDays < maxDays) { long mid = (minDays + maxDays) / 2; long unit = 0; for (long machine : machines) { unit += mid / machine; } if (unit < goal) { minDays = mid+1; } else { result = mid; maxDays = mid; } } return result; }

egri_rasid + 0 comments You can improve this by setting maxDays to machines[0]*goal No need to set it higher

chirukuharsha + 2 comments #include <stdio.h> 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; }

cockhair029 + 0 comments ITS WOKING

tanu1 + 0 comments can you please explain it

marcinbudny93 + 0 comments C++ solution:

long lower_bound(std::vector<long>& m, long goal, long left, long right) { if (left > right) return left; long mid = (left+right)/2; unsigned long long result{0}; for(auto x : m) result += mid/x; if (result >= goal) return lower_bound(m, goal, left, mid-1); else return lower_bound(m, goal, mid+1, right); } long minTime(vector<long> machines, long goal) { return lower_bound(machines, goal, 0L, std::numeric_limits<long>::max());

carlosbf + 2 comments Here is my c++ solution

long compute_time_rec(vector<long> m, long p, long min, long max); // ======== SOLUTION ======== long minTime(vector<long> machines, long goal) { sort(machines.begin(), machines.end()); return compute_time_rec(machines, goal, machines.front()*goal/machines.size(), machines.front()*goal); } long compute_time_rec(vector<long> machines, long production_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 >= production_goal) return compute_time_rec(machines,production_goal, min_days, mid); else return compute_time_rec(machines, production_goal, mid+1, max_days); }

Bonus iterative solution

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; }

himanshu_1 + 1 comment Can you explain why min_days =1 .Why not min_days=machines[0]*goal?

carlosbf + 2 comments The expression in max_days meant to be an upperbound, 1 is a lower bound for any machines. So the solution could also be in the range [1,machines[0]*goal) Consider this counterexample; machines={1,3,5,7} , goal=5 if we set min_days =1*5. then our solution becomes 5. But the optimal solution is 4 when machine_0 produces 4 and machine_1 produces 1.

himanshu_1 + 0 comments Got it. Thanks!

labels + 3 comments Your upper bound is too high. it should be

`machines.front()*goal`

instead.The longest possible production times are the ones that produce all the items on a single machine. Of those, the shortest is the one that produces all items using the

*fastest*machine.

fynx_gloire + 1 comment Hello, can you please explain your logic, I do not quite understand it

thx in advance

carlosbf + 0 comments Hey I took a break from hackerrank sorry for the late reply. What I did was looking for the minimum number of days to produce an output with binary search.

Computing the the output for n days takes linear time. And there is no way to avoid this. So I came up with a lowerbound and upperbound to what the number of days could be since the output is nondecreasing binary search works fine.

rcl0000zk + 1 comment C# .NET Solution:

static long minTime(long[] machines, long goal) { Array.Sort(machines); long maximumPossibleTime = machines.Last() * goal / machines.Length; long minimumPossibleTime = machines.First() * goal / machines.Length; long numberOfDays = BinarySearchForOptimalTime(machines, goal, minimumPossibleTime, maximumPossibleTime); return numberOfDays; } static long BinarySearchForOptimalTime(long[] machines, long goal, long min, long max) { long mid = 0, noOfItems; while(min<max) { mid = min + (max - min) / 2; noOfItems = CalculateItemsForGivenDays(machines, mid); if(noOfItems < goal) min = mid + 1; else max = mid; } return max; } static long CalculateItemsForGivenDays(long[] machines, long days) { long items = 0; for(int i=0; i<machines.Length; i++) items += (days/machines[i]); return items; }

elcuatefraga + 0 comments Shorter:

`long min = machines.Min() * goal / machines.Length; long max = machines.Max() * goal / machines.Length; while (min < max) { long days = (max + min) / 2; if (machines.Sum(x => days / x) < goal) min = days + 1; else max = days; } return (long)max;`

prasadgaikwad777 + 1 comment very simple python code

`def minTime(machines, goal): production = 0 days = 0 while(production<goal): days +=1 production += sum([1 for i in machines if(days%i)==0]) return days`

TylerChenhall + 0 comments If all the machines are slow, then we'll waste a lot of time doing needless computation for this method.

For example, what if we have a goal of 10^9, only 1 machine, and it produces an item every 10^9 days? Your code will have to increment the "days" variable 10^18 times! This is far too slow

pc_pramukh99 + 0 comments long minTime(vector<long> machines, long goal) { map<int,int> m; for(int i=0;i<machines.size();i++){ m[machines[i]]++; } // for(const auto &x : m){ // cout << x.first << " "<< x.second << endl; // } long production =0; long days =0; map<int,int>::iterator it; while(goal > production){ days++; long cprod = 0; for(it = m.begin();it!=m.end();it++){ if(days/it->first==0) break; cprod+=(days/it->first)*(it->second); } production = cprod; } return days; }

can anyone help me 5,7,8,9 testcase running timeout

Sort 68 Discussions, By:

Please Login in order to post a comment