Given a circular road and a set of petrol pumps located at distances d1 d2 ... dn away from each other and supplying p1 p2 p3 ... pn amounts of fuel and your vehicle has a mileage of 1km/l. Determine the feasibility of going around the path starting with zero fuel. Find a point from which you can start and complete the cycle given that you have zero initial fuel.
This will be O(n) algorithm.
Start from a random node say i...check till the last node it reach.
Two case:
1: Either it reach to last node. And current node i is result.
2. It stopped at node j.
Then start from node j+1. to find where we can reach all the node by
above algorithm.
No Node from i to j can complete the traversal, because each node will start with 0 petrol. While traversing from i we always reached that node >= 0. So that condition is already checked.
This will be O(n) algorithm.
Start from a random node say i...check till the last node it reach.
Two case:
1: Either it reach to last node. And current node i is result.
2. It stopped at node j.
Then start from node j+1. to find where we can reach all the node by
above algorithm.
No Node from i to j can complete the traversal, because each node will start with 0 petrol. While traversing from i we always reached that node >= 0. So that condition is already checked.
Comments
Post a Comment