Easy and simple proof with Python solution.


  • 2

    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.

    0_1468366781051_image.png

    II. When sum(i, j) < 0, start = i + 1
    Two proof:

    1. 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.
    2. 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
    

  • 0
    O

    total gas\ge total cost, first line, typo.😊


  • 0

    @ouqi fixed, thanks.


  • 0
    R

    When total cost >= total gas, there is always a solution.

    Are you sure this is the case? That means we don't have enough gas to make a full circuit.


  • 0

    @rach3lyen fixed


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.