For any gas pump, when your car arrives, it contains 0 or more gas. So, for each gas pump, the worst case is starting from that pump.
Then, if we starting from pump A1, passed A2 - Ak and failed at Ak+1. for A1 to Ak, we can not pass Ak+1 starting from any of them. So we try start from Ak+1. This could be solved in liner time. finding a possible start pump use O(n) and prove it use another O(n). -weiq On Sat, Jan 29, 2011 at 9:47 PM, nishaanth <nishaant...@gmail.com> wrote: > @Wei.Qi.... Can you clarify when your algorithm terminates and also what > is the running time of the algorithm ? > > > On Sun, Jan 30, 2011 at 9:46 AM, yq Zhang <zhangyunq...@gmail.com> wrote: > >> can you prove it? >> >> On Jan 29, 2011 6:38 PM, "Wei.QI" <qiw...@gmail.com> wrote: >> > >> > Starting with any pump A, try to finish the circle, if at pump B that >> can not reach pump B+1, it means all pumps from A to B can not finish the >> circle (it will go broke at pump B), then just start with B+1. After go >> through all the pumps start from some pump, we got an answer. if we go back >> to pump A and later, still can not find an answer, there is no answer. >> > >> > On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava < >> richi.sankalp1...@gmail.com> wrote: >> >> >> >> I'm sure you have misstated the problem statement >> >> >> >> just find out the total path length and return the first petrol pump >> >> which gives you the required milage >> >> go greedy >> >> >> >> On Jan 28, 5:09 pm, bittu <shashank7andr...@gmail.com> wrote: >> >> > There are N petrol pumps along a circular path. Every petrol pump >> >> > gives some amount of fixed petrol. Need not to be unique and in no >> >> > particular order means it is random. We have a car and we need to >> find >> >> > a petrol pump which can provide so much of petrol that we can take a >> >> > full of the circle. Mileage of car is fixed. >> >> > Distance between adjacent petrol pumps are given. >> >> > >> >> > Thanks & Regards >> >> > Shashank >> >> >> >> -- >> >> You received this message because you are subscribed to the Google >> Groups "Algorithm Geeks" group. >> >> To post to this group, send email to algogeeks@googlegroups.com. >> >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> >> 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 algogeeks@googlegroups.com. >> > To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> > 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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > S.Nishaanth, > Computer Science and engineering, > IIT Madras. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 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.
