There are n petrol bunks arranged in circle. Each bunk is separated from the rest by a certain distance. You choose some mode of travel which needs 1litre of petrol to cover 1km distance.

Problem

There are n petrol bunks arranged in circle. Each bunk is separated from the rest by a certain distance. You choose some mode of travel which needs 1litre of petrol to cover 1km distance. You can’t infinitely draw any amount of petrol from each bunk as each bunk has some limited petrol only. But you know that the sum of litres of petrol in all the bunks is equal to the distance to be covered.
ie let P1, P2, … Pn be n bunks arranged circularly. d1 is distance between p1 and p2, d2 is distance between p2 and p3. dn is distance between pn and p1.Now find out the bunk from where the travel can be started such that your mode of travel never runs out of fuel.

Solution:

To understand the solution of problem first understand the below inequalities.
if a >= 0, a+b >=0, a+b+c>=0 and a+b+c+d < 0
Then following inequalities also hold true
b+c+d < 0, c+d<0 and d < 0

This would mean that when we start from any point (say P) and after moving through some tanks we run out of fuel at point (Say Q), then any points between P and Q cannot be starting point (including Q) so our next search has to start from Q+1. We will save this point as our starting point.
Note: We only need to consider till end point (assuming non-circular) because, the sum of all values would be zero, so we will be able to reach our current starting point from first point if we can reach end point from current starting point.

Now using array P[1..N]: Petrol capacity and D[1..N]: Distance between tanks
Compute array C[1..N] such that C[i] = P[i] - D[i], C[i] can be +ve, -ve or zero.

We start with C[1] and keep a variable sum to store sum of C[i]s so far. At any stage if C[k] makes are sum < 0, we start from k+1 and set sum = C[K+1]

Psuedo code:
index = 1;
sum = 0
result = index;
while(index <= N) {
     sum += C[index];
     if(sum < 0) {
         sum = 0;
         result = index + 1;
     }
     index++;
 }
 if(index >= N) {
     NO SOLUTION POSSIBLE;
 } else {
     result store our starting point
 }