ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

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

prodevelopertutorial November 27, 2018

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:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2020 ProDeveloperTutorial.com
Get top courses from: Educative.io