A courier drives a fixed clockwise loop past n fuel depots numbered 0 to n-1. At depot i the courier picks up gas[i] litres, and driving from depot i to the next depot (i+1) mod n burns cost[i] litres. The tank starts empty at the chosen depot and must never drop below zero at any point of the loop.
Among all depots from which the entire loop can be completed, output the smallest index. If no depot works, output -1.
Line 1: an integer n.
Line 2: n space-separated integers, the gas values.
Line 3: n space-separated integers, the cost values.
A single integer: the smallest valid starting depot index (0-based), or -1 if none exists.
Example 1
Input
5 1 2 3 4 5 3 4 5 1 2
Expected
3
Explanation
Starting at depot 3, the tank stays non-negative all the way around, and no smaller index works, so the answer is 3.
Example 2
Input
2 2 2 3 3
Expected
-1
Explanation
Total gas 4 is less than total cost 6, so the loop can never be completed: -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →