[quote]"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."[/quote]
So , we just need to find a petrol pump which takes you "just" a full circle , not anything ahead , not anything behind . 1)Sort the petrol he can get from maximum stations .If the total distance is not given , calculate this while sorting . Binary search over this array for the required distance . complexity :-O(nlogn+k) 2)Hash it !! keep a hash for all the distance in some boolean array .now find out the one which can get you the full circle , O(n) complexity . Not space efficient . 3)Using dynamic programming . dp[i][j] :-The distance we still need to cover (j) .while , we are on the started at the ith station . dp[i][0]:- answer , we need to look at the all the dp pairs for the answer . dp[i][j]= min(dp[i+next[i][j-d[i][next[i]]]) Basically a BFS . O(n^2) . worst case . -- 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.
