Check if there is a gas stations along a circular route, solution with explanation in CPP

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a motorcycle with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Example 1:

Input: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start from station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
From then go to station 4. Current tank = 4 - 1 + 5 = 8
From then go to station 0. Current tank = 8 - 2 + 1 = 7
From then go to station 1. Current tank = 7 - 3 + 2 = 6
From then go to station 2. Current tank = 6 - 4 + 3 = 5
From then go to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

As the solution is said to be unique, we can come to a conclusion, if we cannot reach to the next station, then we start from the next station and check if there exist a solution.

To reach to the next station, we should be having a fuel. If we don’t have fuel, then we start from the next station.

Some of the points to remember is:
1. If the sum of the gas is greater than the sum of the cost, then there exist a unique solution.
2. The tank should not be negative, if it is, then restart the path from the station where the tank became negative.

Hence this can be done in O(n) time.

Solution in C++

#include<iostream>
#include<vector>

using namespace std;
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) 
{
    int tank=0;		// Current gas value
    int total=0; 	// To store the value of current_gas - cost + next_gas 
    int start=0; 	// Start station

    for(int i=0; i<gas.size(); i++) 
    {
        int current = gas[i]-cost[i];
        tank += current;
        total += current;
        if(tank < 0) 
        {
            start = i+1;
            tank = 0;
        }
    } 
    return total < 0 ? -1 : start;
}


int main()
{
	vector<int> gas;
	gas.push_back(1);
	gas.push_back(2);
	gas.push_back(3);
	gas.push_back(4);
	gas.push_back(5);

	vector<int> cost;
	cost.push_back(3);
	cost.push_back(4);
	cost.push_back(5);
	cost.push_back(1);
	cost.push_back(2);

	int result = canCompleteCircuit(gas, cost);

	if(result)
		cout<<"There is a path, the starting station is = "<< result<<endl;
	else
		cout<<"There is no path"<<endl;


	return 0;
}

Output:

There is a path, the starting station is = 3

List Of Tutorials available in this website: