My solution, a) First sort the distances. b) We will consider the first 2 minimum numbers.. They are definitely the distances between the 3 nodes... c) Find the sum of the first 2 minimum numbers.. If this sum is outside "n" then we simply return all the nodes less than "n" else remove that sum and repeat this step by finding the next possible minimum sum.
Thanks, Swathi > On Thu, Jul 7, 2011 at 6:30 PM, Dumanshu <[email protected]> wrote: > >> Initially we can sort the array in O(nlogn) and then given a max >> value, find a pair (x,y) in O(n). here n is also of quadratic order if >> taken in terms of no. of milestones. >> >> On Jul 7, 5:52 pm, Dumanshu <[email protected]> wrote: >> > how about this? >> > given n milestones >> > >> > 1.find max number from the array and delete it. >> > 2.now find any (x,y) both from the array such that x+y == max. >> > 3. put min(x,y) in the front of output array, delete y from array and >> > if(sizeof(output array)==(n-2)) >> > put x also in front of output array and exit. >> > else >> > goto 1 with max=x. >> > >> > complexity is screwed up. :( >> > any counter case? >> > >> > On Jul 7, 1:23 pm, Akshata Sharma <[email protected]> wrote: >> > >> > >> > >> > > There is a straight roads with 'n' number of milestones. You are given >> an >> > > array with the distance between all the pairs of milestones in some >> random >> > > order. Find the position of milestones. >> > > Example: >> > > Consider a road with 4 milestones(a,b,c,d) : >> > > a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d >> > > Distance between a and b = 3 >> > > Distance between a and c = 8 >> > > Distance between a and d = 10 >> > > Distance between b and c = 5 >> > > Distance between b and d = 7 >> > > Distance between c and d = 2 >> > > All the above values are given in a random order say 7, 10, 5, 2, 8, >> 3. >> > > The output must be 3,5,2 or 2,5,3- Hide quoted text - >> > >> > - Show quoted text - >> >> -- >> 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.
