Uncategorized

Gas Problem | LeetCode

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;
}

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s