*Note: This was reblogged from my own blog : algorithmpractice.wordpress.com. You may wish to head over there to find more such entries.*

There’s a pretty famous problem given on LeetCode under the name of “Gas Problem”. Here’s the question:

You’re driving a car and have to visit N petrol pumps along the way. The **N** petrol pumps have a certain amount of petrol *pet[i]* each for you. Each of the petrol pumps is at a distance *dist[i]* from each other. You must choose a starting point such that you can complete the whole loop without running out of gas . Assume 1 unit of petrol lets you drive 1 unit distance.

Try and think about the solution.

Think of it like this : We need to reach the end element anyhow. Thus, whatever our start point, it must be able to reach the last station (n-1) . So iterate through the array and whenever the sum becomes negative, set the starting point as the station next to this point. Finally, iterate through the array and check whether this point can work. If it doesn’t, there isn’t any solution.

#define rep(i,n) for(int i=0;i<n;i++)
//given petrol pumps with amount of petrol they have, and the distance between them, find the start point from where you can complete a circular tour
int startPoint(int *pet,int *dist,int n){
// sum will store the net petrol we have till now
int sum=-1;
int ind=-1;
rep(i,n){
if(sum<0)
ind=i,sum=0;
sum+=pet[i]-dist[i];
}
//Whenever sum goes to less than 0 we set the next pump as our new starting point
bool flag = false;
//we confirm that the index thus found can finish the loop
rep(i,n){
sum+=pet[(ind+i)%n]-dist[(ind+i)%n];
if(sum<0)
flag=true;
}
if(flag)
return -1;
else return ind;
}
int main()
{
int arr[100];int n;
scanf("%d",&n);
int *pet = new int[n]
int *dist= new int[n];
rep(i,n)
scanf("%d",&pet[i]);
rep(i,n)
scanf("%d",&dist[i]);
int ans= startPoint(pet,dist,n);
if(ans==-1)
cout<<"Not possible"<<endl;
else cout<<"We start at "<<ans<<endl;
return 0;
}

### Like this:

Like Loading...

*Related*