Finally, coordinating a relay road-trip with limited fuel at each rest stop, Mitu needs to find a valid starting stop from which the whole circular route can be completed without running out of gas. Given N gas stations arranged in a circle, each with gas[i] available and cost[i] to travel to the next station, determine the starting station index (0-indexed) from which you can complete the full circular tour, or print -1 if impossible. Solve in O(N), not O(N^2).
Input
Line1: N. Line2: N gas values. Line3: N cost values.
Output
Starting index (0-indexed), or -1.
Constraints
1 ≤ N ≤ 10^5
Sample Input
5 1 2 3 4 5 3 4 5 1 2
Sample Output
3
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.