can any one give me anexample which takes worst case of this problem On Mon, Mar 26, 2012 at 1:56 PM, Arpit Sood <[email protected]> wrote:
> @ankur +1 > correct algo, can be done in just one pass. > > On Mon, Oct 24, 2011 at 11:03 PM, Ankur Garg <[email protected]> wrote: > >> I think this can be solved like this . >> Start from the first petrol pump i.e first point in the circle . Now if >> the petrol finishes befor reaching the second petrol pump that means we >> chose the incorrect point . So , choose second petrol pump now. If u reach >> third, fill ur tanker and move to 4th . Now if before 4th we again run out >> of petrol that means our choice was incorrect . Start from 4th and so on .. >> If u reach the starting point again this is the choice we need to make >> ..and thats the answer . Programatically , it can be thought of Kadane Algo >> ..(seems to me ..not sure of algo) but I think this way we just make at >> most 2 pass (in case the petrol pump of choice is just before the first >> point ) . >> >> Please comment in case you think its right/wrong >> >> Regards >> Ankur >> >> >> On Mon, Oct 24, 2011 at 10:15 PM, ravindra patel < >> [email protected]> wrote: >> >>> @Nitin, excellent algo. >>> >>> >> if S < 0 && j = i-1 return 0 // I believe this mean there is no >>> solution, you might want to return -1. >>> >>> >>> Thanks, >>> - Ravindra >>> >>> >>> >>> On Mon, Oct 24, 2011 at 8:39 PM, Nitin Garg >>> <[email protected]>wrote: >>> >>>> Lets say the Amount of petrol is Pi and distance to next petrol pump is >>>> Di for ith petrol pump. >>>> >>>> start from i=1, j=1 S =0 >>>> while (i<=n) >>>> S += Pj - Dj; >>>> if S >= 0 && j = i-1 return i >>>> if S < 0 && j = i-1 return 0 >>>> else if S >= 0 j++ mod n; >>>> else if S < 0 j ++ mod n, i = j , S = 0; >>>> >>>> return 0 >>>> >>>> >>>> >>>> it will traverse atmost twice, and hence O(n). no extra space required. >>>> >>>> >>>> On Mon, Oct 24, 2011 at 4:06 AM, Aniket <[email protected]> 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 to 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 post to this group, send email to [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]. >>>>> For more options, visit this group at >>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>> >>>>> >>>> >>>> >>>> -- >>>> Nitin Garg >>>> >>>> "Personality can open doors, but only Character can keep them open" >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To post to this group, send email to [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Regards, > Arpit Sood > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. >
