Point  Fuel  Distance to next point
P1     5     8
P2     3     4
P3     12    7
P4     1     4
P5     7     5

Method 1 : Brute Force

Algo :
1) Start from first point
2) Try to traverse each petrol bunks in next direction.
if not possible. break;

int i,j,st,tr;
int dist[n];
int fuel[n];
num=n;

j=0; //to track index of city/Petrolbunk 

while(j){
  for(i=j;i<n;i++){
     if(fuel[i]-dist[i] < 0) { tr =0 ; break; 
     //we can't start from i th , start from next    
     //city  and make num of traversed city = 0. 
     
     else if (tr == 5){return 1;} // we traversed all cities return True;
     else (tr++);  //else move to next and number of traversed city incremented
  }//for
 j++;
}//whileover

– Here we started from location 0;
if we cant traverse all city, just increment j ( city index) start from next city.

This method takes O ( n ^2 ) as for all city we are trying to travel all cities.

Method 2 : O(n) Time method.

first lets understand method
Start from P1. and store last = last+=fuel-distance Array
before starting last=0;

Point  last = last + fuel-distance (before refueling)
P1     -3 ( 0 + 5 - 8 )
P2     -4 ( -3 + 3 - 4 )
P3      1 ( -4 + 12 - 7)
P4     -2 ( 1 + 1 - 4 )
P5      0 ( -2 + 7 - 5 )

Now as at last we can reach with 0 value.
We can travel this cities with “X” location/city/petrol.
X will be next station of smallest last value. ie : P3 here.
(start from p3, You have 12 lit fuel next station P4 at 7 distance remaining fuel at P4 is 5, from there take 1 unit of fuel now you have 6. next station P5 at distance 4 , remaining fuel at P5 is 2, get 7 units fuel from P5 and go to P1… You can complete cycle.)
Ex. 2 :  Do it your self.

Point Fuel Distance to next point
 P1 3 3
 P2 4 10
 P3 6 2
 P4 3 4
 P5 7 6
 P6 11 9

Thanks to Dhaval for suggesting this Article

Code :

float [] fuel = { 3,4,6,3,7,11 };
float [] dist = { 3,10,2,4,6,9 };
int n = 6;

int FindMinimumPosition()
{
    float last = 1;
    int position = 0;
    float minimumFuel = 1;
    int minimumPosition = 0;

    while (position < n)
    {
        last += fuel[position];
        last -= dist[position];
        position++; // could be n which is past array bounds
        if (last < minimumFuel) {
            minimumFuel = last;
            minimumPosition = position % n; //in case of last station
        }
    }

    return minimumPosition
}

This takes O(n) time complexity + O(n) Space complexity to store “last[n]”
Working Code : http://ideone.com/KVAFfg
If you want to share such question , solution  or your experience of any company, Please do share at admin@gohired.in , As sharing is caring

-IF YOU LIKE OUR EFFORT, PLEASE LIKE AND SHARE OUR FB-PAGE AND SITE