📘

Gas Station

There are n gas stations in a circle. You have gas[i] fuel at station i and it costs cost[i] fuel to travel to the next station.

Return the starting station index if you can travel around the circuit once clockwise, or -1 if impossible.

If a solution exists, it is guaranteed to be unique.

Input:

1,2,3,4,5
3,4,5,1,2

Output:

Reasoning:

We start by calculating the total amount of gas available: $gas_{total} = 1 + 2 + 3 + 4 + 5 = 15$ and the total cost to travel around the circuit: $cost_{total} = 3 + 4 + 5 + 1 + 2 = 15$ .
Since $gas_{total} = cost_{total}$ , it is possible to travel around the circuit once.
We then calculate the cumulative gas level at each station:
- Station 0: $1 - 3 = -2$
- Station 1: $-2 + 2 - 4 = -4$
- Station 2: $-4 + 3 - 5 = -6$
- Station 3: $-6 + 4 - 1 = -3$
- Station 4: $-3 + 5 - 2 = 0$
The starting station index is the one where the cumulative gas level starts to be non-negative, which is station 3.
Therefore, the output is $\boxed{3}$ .

Editor

Python 3.13.1

0/0

Run code to see test results.

📘