Proof of "if total gas is greater than total cost, there is a solution". C++


  • 61

    We prove the following statement.
    If sum of all gas[i]-cost[i] is greater than or equal to 0, then there is a start position you can travel the whole circle.
    Let i be the index such that the the partial sum

    gas[0]-cost[0]+gas[1]-cost[1]+...+gas[i]-cost[i]
    

    is the smallest, then the start position should be start=i+1 ( start=0 if i=n-1). Consider any other partial sum, for example,

    gas[0]-cost[0]+gas[1]-cost[1]+...+gas[i]-cost[i]+gas[i+1]-cost[i+1]
    

    Since gas[0]-cost[0]+gas[1]-cost[1]+...+gas[i]-cost[i] is the smallest, we must have

    gas[i+1]-cost[i+1]>=0
    

    in order for gas[0]-cost[0]+gas[1]-cost[1]+...+gas[i]-cost[i]+gas[i+1]-cost[i+1] to be greater.
    The same reasoning gives that

     gas[i+1]-cost[i+1]>=0
     gas[i+1]-cost[i+1]+gas[i+2]-cost[i+2]>=0
     .......
     gas[i+1]-cost[i+1]+gas[i+2]-cost[i+2]+...+gas[n-1]-cost[n-1]>=0
    

    What about for the partial sums that wraps around?

    gas[0]-cost[0]+gas[1]-cost[1]+...+gas[j]-cost[j] + gas[i+1]-cost[i+1]+...+gas[n-1]-cost[n-1]
    >=
    gas[0]-cost[0]+gas[1]-cost[1]+...+gas[i]-cost[i] + gas[i+1]-cost[i+1]+...+gas[n-1]-cost[n-1]
    >=0
    

    The last inequality is due to the assumption that the entire sum of gas[k]-cost[k] is greater than or equal to 0.
    So we have that all the partial sums

    gas[i+1]-cost[i+1]>=0,
    gas[i+1]-cost[i+1]+gas[i+2]-cost[i+2]>=0,
    gas[i+1]-cost[i+1]+gas[i+2]-cost[i+2]+...+gas[n-1]-cost[n-1]>=0,
    ...
    gas[i+1]-cost[i+1]+...+gas[n-1]-cost[n-1] + gas[0]-cost[0]+gas[1]-cost[1]+...+gas[j]-cost[j]>=0,
    ...
    

    Thus i+1 is the position to start. Coding using this reasoning is as follows:

    class Solution {
    public:
        int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
            int n = gas.size();
            int total(0), subsum(INT_MAX), start(0);
            for(int i = 0; i < n; ++i){
                total += gas[i] - cost[i];
                if(total < subsum) {
                    subsum = total;
                    start = i + 1;
                }
            }
            return (total < 0) ?  -1 : (start%n); 
        }
    };

  • 0
    M

    Could you please explain what does the index j mean here?


  • 0

    j is any index in the range from 0 to i. So the partial sum

    `gas[0]-cost[0]+gas[1]-cost[1]+...+gas[j]-cost[j] + gas[i+1]-cost[i+1]+...+gas[n-1]-cost[n-1]`
    

    is the sum of all the gas[k] - cost[k] for k starts at i+1 and goes to n-1, then goes beyond that and restart from 0, then 1 and finally ends at j.


  • 0
    M

    Does that mean gas[i+1]-cost[i+1]+...+gas[n-1]-cost[n-1]+gas[0] - cost[0]+...+gas[j]-cost[j]? So the partial sum of gas[j+1]-cost[j+1]+...+gas[i]-cost[i] is not included here right?


  • 0

    Yes, you are right.


  • 0
    M

    Appreciate, man! Nice and clean solution.


  • 0

    Thanks for commenting.


  • 0
    X

    Did you consider when there are multiple, same, "min" value of total?


  • 1

    It does not matter, suppose there are multiple minimum values of the partial sum, for example given the gas[i] - cost[i] sequence:

    0, 1, -1, 2, -2, 3, -3, 0
    

    the partial sum sequence is

    0, 1, 0, 2, 0, 3, 0, 0
    

    As you can see that the partial sum sequence has multiple minimum values of 0, corresponding to index i = 0, 2, 4, 6, 7, so the start position can be start = i + 1 = 1, 3, 5, 7, 0. My algorithm just picks the first one i = 0, start = 1 to return.


  • 1
    D

    Your Solution is incorrect.
    It may have got Accepted here on LeetCode.
    But it fails for following Input :
    Gas : [383,521,491,907,871,705]
    Cost : [96,197,592,67,77,641]


  • 0
    D

    Its failing for any input, where answer is 0. Failed even for this :
    Gas : [1,2,3,4,5,6]
    Cost : [1,2,3,4,5,6]


  • 3

    Thank you very much for commenting.

    In your first example,

    gas[0] - cost[0] = 383 - 96 = 287, 
    
    gas[1] - cost[1] = 521 - 197 = 324, 
    
    gas[2] - cost[2] = 491 - 592 = -101, 
    
    gas[3] - cost[3] = 907 - 67 = 840, 
    
    gas[4] - cost[4] = 871 - 77 = 794, 
    
    gas[5] - cost[5] = 705 - 641 = 64,  
    

    What are the partial sums are?

    s[0] = 287;
    
    s[1] = 287 + 324 = 611;
    
    s[2] = 611 - 101 = 510;
    
    s[3] = 510 + 840 = 1350;
    
    s[4] = 1350 + 794 = 2144;
    
    s[5] = 2144 + 64 = 2208;
    

    Which one is the smallest partial sum? It is s[0].

    So my program should return position 1. I understand that for this example you can start at pretty every position except 2. But starting at where the partial sum is the smallest will guarantee that the car can travel a whole circle even in the worst case.

    In your second example,

    gas[0] - cost[0] = 1 - 1 = 0, 
    
    gas[1] - cost[1] = 2 - 2 = 0, 
    
    gas[2] - cost[2] = 3 - 3 = 0, 
    
    gas[3] - cost[3] = 4 - 4 = 0, 
    
    gas[4] - cost[4] = 5 - 5 = 0, 
    
    gas[5] - cost[5] = 6 - 6 = 0,  
    

    What are the partial sums are?

    s[0] = 0;
    
    s[1] = 0;
    
    s[2] = 0;
    
    s[3] = 0;
    
    s[4] = 0;
    
    s[5] = 0;
    

    Which one is the smallest partial sum? Everyone!. Your can return 0, 1, 2, 3, 4, 5! My program simply chooses 1 to return, it is not incorrect, it is just not designed to return all the possible start positions.

    How about you try the following extreme example?

    gas:[1,1,3]
    
    cost:[2,2,1]
    

    I will guarantee you that it will return 2. Which in this case is the ONLY correct position to start.

    I hope this answered your concern.


  • 0

    Or you can try this example

    gas:[3,1,1]
    cost:[1,2,2]
    

    The ONLY correct position is 0, my program will return 0 too.


  • 0
    D

    Sorry. And Thanks for clarifying. :)


  • 0

    Great proof, Shana chan!


  • 0

    @Misaka-10032 Thanks, Misaka chan.


  • 0
    R

    @XBOX360555

    do you know why the question says "Note: solution is guaranteed to be unique"?


  • 0

    @randy_wales I think in general case, it may have multiple solutions, to say "solution is guaranteed to be unique" means your code is only going to be tested in those special cases where solution is unique, so you don't have to worry about multiple solutions.


  • 0
    T

    perfect! excellent!


  • 0
    M

    How did you get

    gas[0]-cost[0]+gas[1]-cost[1]+...+gas[j]-cost[j] + gas[i+1]-cost[i+1]+...+gas[n-1]-cost[n-1]
    >=
    gas[0]-cost[0]+gas[1]-cost[1]+...+gas[i]-cost[i] + gas[i+1]-cost[i+1]+...+gas[n-1]-cost[n-1]
    

Log in to reply
 

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