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

• 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);
}
};``````

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

• `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`.

• 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?

• Yes, you are right.

• Appreciate, man! Nice and clean solution.

• Thanks for commenting.

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

• 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.

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]

• 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]

• Thank you very much for commenting.

``````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.

``````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.

• 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.

• Sorry. And Thanks for clarifying. :)

• Great proof, Shana chan!

• @Misaka-10032 Thanks, Misaka chan.

• @XBOX360555

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

• @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.

• perfect! excellent!

• 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]
``````

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