2nd part of ankit's solution can be easily done in O(n) after sorting of array
i = 0, j = n-1 while(i < j) if a[i]+a[j] == x , i and j are indexes of the elements if a[i]+a[j] > x decrement j if a[i]+a[j] < x increment i On Tue, Jun 28, 2011 at 6:49 PM, Shachindra A C <[email protected]>wrote: > @sagar : oops ! No need of sorting. Thank you for pointing out :) > > > On Tue, Jun 28, 2011 at 6:41 PM, sagar pareek <[email protected]>wrote: > >> @Shachindra >> If you are using binary tree then why are you doing sorting first? >> >> @ANKIT >> Yes you can't do searching of sum of two numbers in less then O(n*n). >> >> On Tue, Jun 28, 2011 at 6:23 PM, Shachindra A C <[email protected]>wrote: >> >>> @ankit : I'm pretty confident that the second part of your solution >>> cannot be done in O(n) time. Correct me if I am wrong!! Nevertheless, the >>> overall time complexity remains O(n*log(n)), as you pointed out. >>> >>> >>> On Tue, Jun 28, 2011 at 5:59 PM, Shachindra A C >>> <[email protected]>wrote: >>> >>>> @Ankit >>>> Can you please explain the method to get the answer to the second >>>> subpart of your solution in O(n) time? >>>> >>>> My solution to solve the problem in O(n log(n)) time is as follows: >>>> >>>> Insert the nodes of the sorted array into a binary tree. Then start with >>>> the first node. Subtract the value of the node from X. Then search for the >>>> result of the subtraction in the binary tree. This can be done in O(log n) >>>> time, giving O(nlogn) for the overall complexity of the second subproblem. >>>> >>>> Please explain your logic. >>>> >>>> >>>> On Tue, Jun 28, 2011 at 5:48 PM, Nitish Garg >>>> <[email protected]>wrote: >>>> >>>>> Can you please explain how to solve the 2nd question? >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Algorithm Geeks" group. >>>>> To view this discussion on the web visit >>>>> https://groups.google.com/d/msg/algogeeks/-/5C-1NnideVgJ. >>>>> >>>>> 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. >>>>> >>>> >>>> >>>> >>>> -- >>>> Regards, >>>> Shachindra A C >>>> >>>> >>> >>> >>> -- >>> Regards, >>> Shachindra A C >>> >>> -- >>> 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. >>> >> >> >> >> -- >> ** >> Regards >> SAGAR PAREEK >> COMPUTER SCIENCE AND ENGINEERING >> NIT ALLAHABAD >> >> -- >> 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. >> > > > > -- > Regards, > Shachindra A C > > -- > 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. > -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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.
