Circular Route Fuel Station

MEDIUM20 pts

Imagine a circular highway with n fuel stations positioned along the route. Each station i provides a specific amount of fuel given by fuel[i] units, and traveling from station i to station (i + 1) % n consumes consumption[i] units of fuel.

You have a vehicle equipped with an infinitely large fuel tank that starts completely empty. Your goal is to determine the starting station index from which you can begin your journey and successfully complete one full clockwise circuit of the highway, returning to your starting point.

Objective: Return the index of the starting station if such a complete circuit is possible. If no valid starting position exists that allows completing the full loop, return -1.

Key Constraints:

You must travel in the clockwise direction only
Your vehicle starts with an empty tank at the chosen station
At each station, you first refuel, then attempt to travel to the next station
Your tank cannot hold negative fuel at any point during the journey
If a solution exists, it is guaranteed to be unique

Example

Input

fuel = [1,2,3,4,5]
consumption = [3,4,5,1,2]

Output

3

Explanation

Starting at station index 3: • Begin at station 3: Tank = 0 + 4 = 4 units • Travel to station 4: Tank = 4 - 1 + 5 = 8 units • Travel to station 0: Tank = 8 - 2 + 1 = 7 units • Travel to station 1: Tank = 7 - 3 + 2 = 6 units • Travel to station 2: Tank = 6 - 4 + 3 = 5 units • Travel to station 3: Tank = 5 - 5 = 0 units The journey is completed successfully, so return 3.

Example

Input

fuel = [2,3,4]
consumption = [3,4,3]

Output

-1

Explanation

No valid starting station exists: • Starting at station 0: Tank = 2 - 3 = -1 (cannot proceed) • Starting at station 1: Tank = 3 - 4 = -1 (cannot proceed) • Starting at station 2: Refuel 4, travel to 0 (cost 3) → Tank = 4 - 3 + 2 = 3 Then station 0 to 1: Tank = 3 - 3 + 3 = 3, then 1 to 2: 3 - 4 = -1 (fails) Total fuel (9) < Total consumption (10), so completing the circuit is impossible.

Example

Input

fuel = [5,1,2,3,4]
consumption = [2,3,4,1,1]

Output

3

Explanation

Starting at station index 3: • Begin at station 3: Tank = 0 + 3 = 3 units • Travel to station 4: Tank = 3 - 1 + 4 = 6 units • Travel to station 0: Tank = 6 - 1 + 5 = 10 units • Travel to station 1: Tank = 10 - 2 + 1 = 9 units • Travel to station 2: Tank = 9 - 3 + 2 = 8 units • Travel to station 3: Tank = 8 - 4 = 4 units The journey is completed successfully with 4 units remaining.

Accepted0/0·0% Acceptance

Constraints

n == fuel.length == consumption.length
1 ≤ n ≤ 10⁵
0 ≤ fuel[i], consumption[i] ≤ 10⁴
The input is generated such that if an answer exists, it is unique.

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

gas =

[1,2,3,4,5]

cost =

[3,4,5,1,2]

Circular Route Fuel Station

Hints

Circular Route Fuel Station

Hints