Petrol Bunks in Circle

There is a circular road, and there are n petrol bunks at different places on that road. The petrol bunk i has enough fuel by which one can travel f_i distance. The distance from the petrol bunk i to i+1 is d_i.

You have a car with empty fuel tank, and you need to find a place from where you can start and travel by that road and reach the same place.























Solution:

The distance from first bunk to second is D1, and second to third is D2 and so on.
The distance that can be travelled by the fuel in the first bunk is F1, and from the second bunk, it is F2 and so on.

If F1 < D1, then we cannot start from the first bunk.
If F1 + F2 < D1 + D2, then we cannot start from the first or second bunks.
Similarly, if F1 + F2 + F3 < D1 + D2 + D3, then we cannot start from the first, second or third bunks.

Wherever we reach the fuel to be less than the distance, we have to skip all those bunks, and have to move to the next bunk and repeat the same thing.


Code:

#include<<stdio.h>

int findStart(int distance[], int capacity[], int n)
{
 int c=0, d=0, st=0, i;
 for(i=0; i<n; i++) {
  c+=capacity[i];
  d+=distance[i];
  if(c<d) {
   st = i+1;
   c=0;
   d=0;
  }
 }
 if(st != 0) {
  for(i=0; i<st; i++) {
   c+=capacity[i];
   d+=distance[i];
   if(c<d) {
    return -1;
   }
  }  
 }
 return st;
}

main()
{
 int distance[] = {10,20,30,40,50,60};
 int capacity[] = {11,21,10,50,51,71};
 int result = findStart(distance, capacity, 6);
 printf("%d \n", result);
}