We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

Consider the amount of fuel you have in your tank as a function of the amount of stations you have passed (the integral of the change in fuel {gained - used} per station results in the amount of fuel for every station, the fundamental theorem of calculus). Now: this function has to be positive for every station because you cannot ever have negative fuel in your tank. This only happens whenever you start at a global minimum of this function. You are essentially shifting the function vertically, setting it to zero at your starting point and if this is the lowest point then all other points will be positive.

This is assuming that a full circle will not result in a net fuel loss (then you cannot complete the circle) and furthermore that there are no more than 1 global minima (then you get stuck with exactly 0 fuel at the position of the second global minimum).

Your solution's complexity is O(N^2) as you will start from
0th to Nth
1st to 0th
2nd to 1st
3rd to 2nd
...
Nth to N-1th
each step will take N time and there are N step. So the worst case time complexity will be O(N^2). Correct me if I am wrong. I have done this way and I have used loop inside loop and it's time complexity is O(N^2).

I don't think that's the method Gladdyu is proposing. His method would have worst case complexity of O(N), because all you do is go through the loop once, and at each stop record the total amount of gas up to that point, which could be negative if there is a greater amount of distance traveled to that point than gas gained. Then the point with the minimum amount of gas is the answer.

Gladdyu, I think there's one error in what you said though; if there are two global minima, it doesn't matter, because that would just mean that you'd get to the second minima with 0 gas, but gain however much gas is there, so you can keep going.

without any investigation my guess is a mod, persumable because you linked a solution of some sort. They should do a [comment deleted because xyz] not just ninja remove them. Again this speculation.

## Truck Tour

You are viewing a single comment's thread. Return to all comments →

Consider the amount of fuel you have in your tank as a function of the amount of stations you have passed (the integral of the change in fuel {gained - used} per station results in the amount of fuel for every station, the fundamental theorem of calculus). Now: this function has to be positive for every station because you cannot ever have negative fuel in your tank. This only happens whenever you start at a global minimum of this function. You are essentially shifting the function vertically, setting it to zero at your starting point and if this is the lowest point then all other points will be positive.

This is assuming that a full circle will not result in a net fuel loss (then you cannot complete the circle) and furthermore that there are no more than 1 global minima (then you get stuck with exactly 0 fuel at the position of the second global minimum).

Your solution's complexity is O(N^2) as you will start from

0th to Nth

1st to 0th

2nd to 1st

3rd to 2nd

...

Nth to N-1th

each step will take N time and there are N step. So the worst case time complexity will be O(N^2). Correct me if I am wrong. I have done this way and I have used loop inside loop and it's time complexity is O(N^2).

I don't think that's the method Gladdyu is proposing. His method would have worst case complexity of O(N), because all you do is go through the loop once, and at each stop record the total amount of gas up to that point, which could be negative if there is a greater amount of distance traveled to that point than gas gained. Then the point with the minimum amount of gas is the answer.

Gladdyu, I think there's one error in what you said though; if there are two global minima, it doesn't matter, because that would just mean that you'd get to the second minima with 0 gas, but gain however much gas is there, so you can keep going.

Yep, you're correct!

Is there a comment from Gladdyu im missing? He isnt purposing an algorithm anywhere I can see (a required element for their to be an upper bound).

It appears as if some of my comments got deleted by someone...

without any investigation my guess is a mod, persumable because you linked a solution of some sort. They should do a [comment deleted because xyz] not just ninja remove them. Again this speculation.

Thanks for the update.

I didnt understand your solution. Can you please explain again? I solved it with O(N^2). Thanks.

Clarification - You start one station after the station you see the global minimum so you never hit the global minimum.

Nice explanation !!!

I have read that it is impossible to find a global minimum for any arbitary function.Could it be a case here? http://mathworld.wolfram.com/GlobalMinimum.html

Here the values of the function at all possible indices (this is the key) are given.So all you need to do is to find the minimum by traversing once.