Gas Station
There are a total of n gas stations along a clockwise, circular route, and
for the ith gas station (starting from 0), there are gas[i] litre of gas stored.
The distance between the ith gas station and the i + 1th gas station is dist[i].
You have a car, and you would like to travel clockwise starting from any gas station and return to the same gas station. The car has a sufficiently large gas tank, and for each unit of gas, your car can travel a unit distance. Initially, the fuel tank of your car is empty, but you can add fuel from any fuel station for as long as that fuel station has fuel left.
You wonder whether you can successfully travel this way. If so, output the index representing
the starting gas station. Otherwise, output -1. The solution is guaranteed to be unique,
if one exists.
gas = [1, 2, 3, 4, 5] dist = [3, 4, 5, 1, 2]
3
Starting from station 3, the car has 4 gas. It travels to the next station spending
1 gas, leaving 3 gas. Pick up 5 gas, travel to the next station, and leaving 6
gas. For the next three station, there is enough fuel to travel to each one and return
to the starting point.
1 <= len(gas) == len(dist) <= 10^41 <= gas[i], dist[i] <= 10^4