Why it will fail.. let the given sequence be : A<-----1------>B<-------5------->C<------3----->D<-----2----->E A-B : 1 A -C : 6 A -D: 9 A-E : 12 B-C: 5 B-D: 8 B-E: 10 C-D: 3 C-E: 5 D-E: 2
When we sort we will get 1,2,3,5,5,6,8,9,10,12. The first 2 small number are 1 and 2... so out of 4 distances we are interested we got 2 distances... Now sum the first 2 small numbers 1 and 2.. the sum is 3.. We may endup with duplicate "3" if the distances 1 and 2 are adjacent.. When there is no duplicate that means "3" is another edge.. so we got 3 edges.. now we just need another edge.. now sum 1 and 3 we will get 4 there is no number with 4.. so move from 1 to 2.. now sum 2 and 3.. sum is 5.. The 5 is duplicate that means 2 and 3 are adjacent so remove it.. now we got another edge 5... This is how we will proceed till we find all the edges.. Hope i made my point clear... On Thu, Jul 7, 2011 at 10:44 PM, durgesh kumar <[email protected]>wrote: > > > On Thu, Jul 7, 2011 at 6:41 PM, Swathi <[email protected]> wrote: > >> 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 > > > > > dear swathi, > ur solution will fail one of follwing test cases:- > > > A<----------1--------------->B<--------------5-------------->C<-------------3------------->D<------------------------2---------------------------->E > > > > >> >> >> >>> 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. >> > > -- > 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.
