# Find the first circular tour that visits all petrol pumps

But several as here We have one more parameter say fuel or capacity along with distance we can reduce complexity with the help of it.With examples we can understand this.

Ex 1 :

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