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.
At first Glance we can think its travelling salesman problem and hence only in O(n!) or O(2^n * n^2) is possible.
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 :
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 5Algo :
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
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 )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 9Code :
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
}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
