Home > Applied Algorithms, Greedy > The circularly-arranged petrol pump problem.

The circularly-arranged petrol pump problem.

Problem Statement: You are given n petrol pumps arranged in a circle. There is a certain quantity of petrol that is available at each pump. And you are given the amount of petrol required to reach from each station to the next. You have to find out the petrol pump starting at which you can go around and come back to that particular petrol pump.

Can you think up of a quick method of solving this? I can do it in O(n). Let me explain the method. Take any petrol pump randomly as your START. Take the next pump as END. Now you have an available quantity of petrol at START. See if this quantity is enough to reach END, i.e., is available quantity greater than or equal to required quantity. If yes, add the quantity of petrol available at END to your available quantity and then move END one pump ahead. Now perform the same check between available and required. In case available<required, move your START one pump back, adding the quantity of that pump to your available and adding the required from your new START to the old one to your required. Following this method, you’ll finally converge at a pump (i.e., START=END). This is your required petrol pump. 🙂

Since there is no problem in coding this, I’ll just show an example and get done with this.

In this image (if you can’t view the image, you are probably not viewing this post on my blog), each petrol pump has an available quantity of petrol and the required quantity to reach the next pump. Let us start with the solution by randomly picking START as pump C. There, END is pump D.

available = 3, required = 10

Since available < required, move START back to B.

Now, available = 5+3, required = 10+6

Still available < required, move START back to A.

Now available = 5+3+9, required = 10+6+2

Still available < required, move START back to D.

available = 5+3+9+6, required = 10+6+2+5

Now, available = required and START=END. Hence, the required pump is pump D. You can repeat the process starting at any pump and you would get the right answer. 😉

With that, we come to the end of a lengthy explanation of the problem. But I hope all of you understood it. 🙂

Advertisements
  1. Vishal
    February 25, 2013 at 8:11 pm

    This is good !! I think I have read some similar problem which requires same kind of solution , moving the start and end like the way you have done

  2. Rashmi
    February 12, 2014 at 2:43 pm

    The explanation is good. But i feel, ur logic doesn’t work if u consider “B” as starting point and “C” as END Point.

  1. No trackbacks yet.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: