CareerCup

if i suppose that distance d1 is 1km, d2 is 2km, d3 is 3km......dn is nkm and has limited amount of petrol at every bunk say x,and x>1
in that case it would better to start at p1, once he reaches p1 again, he runs out of petrol and can start over again.

f=0 // fuel
d=0 //distance
s=1 //best starting point

for i-> 1 to n
f+=fi
d+=di
if(f < d)
//reset s,f,d
s=i
f=d=0
endif
endfor

output s

O(n)

The cumulative array of petrol should be > cumulative array of distance for every element

distance array 1 3 2 1 3 5
petrol array 1 2 4 3 3 2

If we start at P1,
Cumulative array for distance = 1 4 6 7 10 15
Cumulative array for petrol = 1 3 7 10 13 15

If we start at P3,
Cumulative array for distance = 2 3 6 11 12 15
Cumulative array for petrol = 4 7 10 12 13 15

So P3 is our answer


Create a cumulative array starting from P1. Traverse the array and find the point (Px), where all elements to right of that

have property such that Pi > Di for all i > x AND
Pj > Dj for all j < x

Px+1 is your answer

otherwise not possible.
One example of not possible is

Distance array 2 8 5 4 1 6 2 2
Petrol array 3 5 7 3 5 3 2 2

@ soron
awesome solution
hats off

A rather alternative approach would be construct differential array where diff[i] = p[i] - d[i]. Now try to find cumulative sum in the array starting from position j. In simple case any time sum < 0, we can't further travel from that point. We need to increment j and try to find if its feasible solution by fiinding cumulative sum of diff[j...n]+diff[0..j]. This is as good as rotating array at position j and finding the sum. Same effect can be achieved if diff array concatenated twice and finding the solution for it until 'n' elements are found.

petrol array 1 2 4 3 3 2
distance array 1 3 2 1 3 5

diff array 0 -1 2 2 0 -3

diff array concatentated 0 -1 2 2 0 -3 0 -1 2 2 0 -3

j = 0; // potential start position
sum = 0;
for(i = 0; i < 2n && (i -j) < n; ++i) { 
  sum += diff[i];
  if(sum < 0) { 
     j = i + 1;
     sum = 0;
  }    
}

return i == 2n ? -1 : j;