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.
Seeing that the solution to this problem has not yet been clearly explained.
Here is the idea for O(n) solution:
(Sorry for grammatical mistakes)
At any point, we always have total gasoline = ? + a[i].
After travelling to city i+1, we have ? + a[i] - b[i] gas left.
I will find d[i] = a[i] - b[i]. Let's assume that d[] is as follow:
0 1 0 -1 0 0 0 1 -2 0 1.
I analyze d[], start at d[8] = -2, we need ?=2 gasoline to get over i=8.
Let's see if we can get 2 gasoline before we reach i=8.
loop A: (8 -> 7 -> 6 -> ... -> 0 -> 10 -> 9)
(A -> A -> A -> ...)
At d[7]=1, 1 more gas needed.
At d[6]=1, 1 more gas needed.
I will create an array dmin[] to see at which index, gasoline need is fulfilled.
dmin[i%n] = min(d[i%n], dmin[(i+1)%n]) + d[i%n];
if dmin[i] < 0, more gas needed
-1 -1 -2 -2 -1 -1 -1 -1 -2 0 0.
(1 A)
So as we can see, at i=9,10 (dmin[i] >= 0), gasoline need is fulfilled.
This is also where I will start my travel.
(trick: Well, I figure out that we only need 2 A to pass Hackerrank test: A -> A)
About c limit:
if (a[i%n] > c) dmin[i%n] -= (a[i%n] - c);
if (? > c) at one point, no start city is possible.
Because, if at city i, the needed gasoline is more than the tank can store.
Then, no matter which city the car starts, it willl never get past city i.
Before you look at my accepted code, please try to write it first even if it takes a week:
Travel around the world
You are viewing a single comment's thread. Return to all comments →
Seeing that the solution to this problem has not yet been clearly explained. Here is the idea for O(n) solution: (Sorry for grammatical mistakes)
At any point, we always have total gasoline = ? + a[i]. After travelling to city i+1, we have ? + a[i] - b[i] gas left. I will find d[i] = a[i] - b[i]. Let's assume that d[] is as follow: 0 1 0 -1 0 0 0 1 -2 0 1.
I analyze d[], start at d[8] = -2, we need ?=2 gasoline to get over i=8. Let's see if we can get 2 gasoline before we reach i=8. loop A: (8 -> 7 -> 6 -> ... -> 0 -> 10 -> 9) (A -> A -> A -> ...) At d[7]=1, 1 more gas needed. At d[6]=1, 1 more gas needed. I will create an array dmin[] to see at which index, gasoline need is fulfilled.
So as we can see, at i=9,10 (dmin[i] >= 0), gasoline need is fulfilled. This is also where I will start my travel. (trick: Well, I figure out that we only need 2 A to pass Hackerrank test: A -> A)
if (? > c) at one point, no start city is possible. Because, if at city i, the needed gasoline is more than the tank can store. Then, no matter which city the car starts, it willl never get past city i.
Before you look at my accepted code, please try to write it first even if it takes a week: