PIXELBANKv8.2.1
Menu
Sign In

Gas Station

EasyGreedy & Intervals

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.

Example:

Input:
1,2,3,4,5
3,4,5,1,2
Output:
3
Reasoning:
  • We start by calculating the total amount of gas available: gastotal=1+2+3+4+5=15gas_{total} = 1 + 2 + 3 + 4 + 5 = 15 and the total cost to travel around the circuit: costtotal=3+4+5+1+2=15cost_{total} = 3 + 4 + 5 + 1 + 2 = 15.
  • Since gastotal=costtotalgas_{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=−21 - 3 = -2
    • Station 1: −2+2−4=−4-2 + 2 - 4 = -4
    • Station 2: −4+3−5=−6-4 + 3 - 5 = -6
    • Station 3: −6+4−1=−3-6 + 4 - 1 = -3
    • Station 4: −3+5−2=0-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 3\boxed{3}.

Constraints:

  • 1 <= n <= 10^5
  • 0 <= gas[i], cost[i] <= 10^4
Editor

Test Results

0/0
Run code to see test results.