Loading...
Loading...
Loading...
Depots are arranged in a ring. Depot i gives gas[i] fuel, and driving from depot i to the next costs cost[i] fuel. The tank starts empty and has no limit. Print the index of a depot from which you can drive the whole ring once, or -1 if none exists. If an answer exists it is unique.
Example 1
Input
1 2 3 4 5 3 4 5 1 2
Output
3
Example 2
Input
2 3 4 3 4 3
Output
-1
Try the problem first. Open one hint at a time.
If the total gas is below the total cost, the answer is -1.
Scan with a tank. When it goes below zero, no start up to here works, so restart at the next depot.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor