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. 🙂
All About Algorithms 
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
The explanation is good. But i feel, ur logic doesn’t work if u consider “B” as starting point and “C” as END Point.
Could you elaborate on why the logic won’t work?