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 <duman...@gmail.com> 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 <akshatasharm...@gmail.com> 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 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.
