If we need to find the first petrol pump from where we can reach safely to
the whole circle.Then ---
Algo :- remaining[i] = P[i] - D[i]
1- scan the array from left to right,while traversing keep track of two
variables.
a- total no.of points where remaining[i] < 0
b- a pointer to the location next to largest contiguous negative sum
.This is to ensure that while traversing the circle,the points having
maximum negative remaining petrol come in the end
Now if a==0, all points are valid points to start
if( a==total points) there are no valid points to start
else
start from the location pointed to by p.If it satisfies the
condition,then it can be start point.Else no valid points to start.
On Monday, 24 October 2011 16:36:24 UTC+5:30, Aniket wrote:
>
> Suppose there is a circle. You have five points on that circle. Each
> point corresponds to a petrol pump. You are given two sets of data.
>
> 1. The amount of petrol that petrol pump will give.
> 2. Distance from that petrol pump tp the next petrol pump.
>
> (Assume for 1 lit Petrol the truck will go 1 km)
>
> Now calculate the first point from where a truck will be able to
> complete the circle.
> (The truck will stop at each petrol pump and it has infinite
> capacity).
> Give o(n) solution. You may use o(n) extra space.
On Monday, 24 October 2011 16:36:24 UTC+5:30, Aniket wrote:
>
> Suppose there is a circle. You have five points on that circle. Each
> point corresponds to a petrol pump. You are given two sets of data.
>
> 1. The amount of petrol that petrol pump will give.
> 2. Distance from that petrol pump tp the next petrol pump.
>
> (Assume for 1 lit Petrol the truck will go 1 km)
>
> Now calculate the first point from where a truck will be able to
> complete the circle.
> (The truck will stop at each petrol pump and it has infinite
> capacity).
> Give o(n) solution. You may use o(n) extra space.
On Monday, 24 October 2011 16:36:24 UTC+5:30, Aniket wrote:
>
> Suppose there is a circle. You have five points on that circle. Each
> point corresponds to a petrol pump. You are given two sets of data.
>
> 1. The amount of petrol that petrol pump will give.
> 2. Distance from that petrol pump tp the next petrol pump.
>
> (Assume for 1 lit Petrol the truck will go 1 km)
>
> Now calculate the first point from where a truck will be able to
> complete the circle.
> (The truck will stop at each petrol pump and it has infinite
> capacity).
> Give o(n) solution. You may use o(n) extra space.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/9AU0hvBVPcYJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
