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.
I totally agree. But it still got me because it was under the Queues topic and I thought I needed to use a queue. But I ended up not needing to use any advanced container AT ALL.
Don't need integration, minima, or any such. Don't even need a queue or container, really.
Either the problem is solvable or it's not -- but the problem statement doesn't leave room for unsolvable.
Thus assuming it's solvable, and you're looking for the lowest index from which it works, vinay_star_lord's solution (which I came up with on my own) works without a container, i.e., constant space.
Just one more situation: If the global minimum is positive, that means we'll survive the worst case starting from the 0th position itself. So in that case the answer will be station[0].
Otherwise, if the minimum is negative, we return station[min_index + 1].
Truck Tour
You are viewing a single comment's thread. Return to all comments →
This was the absolute easiest problem 'Difficult' problem on this site so far. Possible in linear time and you don't need any queues whatsoever.
Spoiler alert: Integration and global minima.
agreed
agreed
agreed
can anyone explain me about this integration and global minima
How does integration involve over here? Can u plz explain? I m nt getting it!
I dont it too pls explain.
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.
I think the point of the challenge is to solve the problem using a Queue, rather than just trying to solve it using any possible solution.
But when I used a queue it timed out. I did without a queue and it passed all tests.
LMAO
Thanks for the feedback. However, the level of difficulty sometimes varies as perceived by differnet users, to some extent!
Can't be that easy as you failed to solve it using queue, as the problem and category intended!
https://www.hackerrank.com/challenges/truck-tour/forum/comments/128778
I totally agree. But it still got me because it was under the Queues topic and I thought I needed to use a queue. But I ended up not needing to use any advanced container AT ALL.
It's about queues insofar as the input stream is a queue. So, it's a degenerate case.
Don't need integration, minima, or any such. Don't even need a queue or container, really.
Either the problem is solvable or it's not -- but the problem statement doesn't leave room for unsolvable.
Thus assuming it's solvable, and you're looking for the lowest index from which it works, vinay_star_lord's solution (which I came up with on my own) works without a container, i.e., constant space.
Simple Array operation :
Just one more situation: If the global minimum is positive, that means we'll survive the worst case starting from the 0th position itself. So in that case the answer will be station[0]. Otherwise, if the minimum is negative, we return station[min_index + 1].