- Minimum Time Required
- Discussions

# Minimum Time Required

# Minimum Time Required

kennethjjgibson + 12 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.

piggy + 0 comments Hey, Thank you so much for explaining.

leonardoherrera1 + 0 comments That's pretty clever, however when submitting the solution it still says time out :(

ishank991998 + 0 comments Thank you so much for the explaination

sikarwalishere + 0 comments Thanks for such a nice explanation

hiteshbahar + 0 comments [deleted]iamavinashthaku1 + 0 comments A better way of finding minBound and upperBound is as below( C++ ). I've passed all cases without TLE

double fac = 0; for(const long& mi : machines) fac += 1.0/mi; long minDay = goal/fac; long dayDiff = *max_element(machines.begin(), machines.end()); long maxDay = minDay + dayDiff;

bhgupta + 0 comments Thanks @kennethjjgibson your explanation was really helpful. I wouldn't have thought about the starting point, why this problem is even in search category.

kajal_lightbulb1 + 0 comments Thank you for that.

suryan0800 + 0 comments Thank you for the explanation, bro.

shanx12 + 0 comments Good explanation! Thanks

anshultak98 + 0 comments Thank you so much... nice explaination

576392789csj + 0 comments I feel like there can be problem of finding the local optimal result. For example, if the mid point's corresponding production meets the goal however, there might be another point less than mid point meeting goal as well. But another point will be missed.

ayushr2 + 5 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 + 8 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.

nguyenducthong11 + 0 comments Thanks, i will try it by C#.

As simple as possible

v2005_2005 + 0 comments Very simple and incorrect algorithm!

hibernicus + 0 comments I don't think that works. Consider the input of

- 10 machines, each taking 10 days to produce an item
- goal is 1

Average "slope" is 1, but 10 machines still don't produce 1 item every day. After 10 days you will have 10 items, but you still need 10 days to get your first item.

liurenxing1993 + 0 comments Lol this was my solution:

return ceil(round(goal/sum(1/i for i in machines),2))

And I know it doesn't work because the production is discrete and not continuous.

hovhannes_kh + 0 comments Thanks

Persistencia + 11 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 + 6 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.

h351680058 + 0 comments interestingly, if change the first two lines to

`maxday = math.ceil(max(machines)*goal/len(machines)) minday = math.ceil(min(machines)*goal/len(machines))`

instead of

` minday = math.ceil(goal / len(machines)) * min(machines)

maxday = math.ceil(goal / len(machines) * max(machines)) `

you will encounter run time error

bhgupta + 0 comments thanks @sellerdoor your solution helped me understand this problem better.

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.

chinmay_deo7 + 0 comments why is the upperbound = num_days and not num_day-1

otayeby + 0 comments Why did you return

`int(lower_bound)`

isn't the division for`num_days`

floor integer division?

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

Sort 84 Discussions, By:

Please Login in order to post a comment