Gas Station (Proof)

**I. When total cost <= total gas, there is always a solution.**

sum(x, y) = gas[x] - cost[x] + gas[x + 1] - cost[x + 1] + ... + gas[y] - cost[y]

Proof:

We assume that [i, j] is the greatest range sum. Then, starting from *i*, we could travel the loop. Assume in contradiction that starting from *i*, there is a *m* stop the travel due to out of gas. . Thus, since total sum >= 0, sum[i, j] >= 0. Since total sum >= 0, we know *A + B + C > 0*. Since sum(A, B ) <= 0, then C >= 0. Then, sum(C, A) >= 0. Therefore, sum(C, A) will be the greatest range which is contradicted to the assumption.

**II. When sum(i, j) < 0, start = i + 1**

Two proof:

- Since there is always a solution, once we find a range sum < 0, we can let this range be the last range in the whole trip. Then, start = i + 1.
- Since the gain of previous stations are always >= 0, once we find a range sum[i, j] < 0, there is not a k satisfy that range sum[k, j] >= 0. Then, start = i + 1.

```
class Solution(object):
def canCompleteCircuit(self, gas, cost):
"""
:type gas: List[int]
:type cost: List[int]
:rtype: int
"""
totalgas = 0
totalcost = 0
start = 0
balance = 0
for i in xrange(0, len(gas)):
totalgas += gas[i]
totalcost += cost[i]
balance += gas[i] - cost[i]
if balance < 0:
start = i + 1
balance = 0
if totalcost <= totalgas:
return start
return -1
```