@Shachindra: The second part of my solution can definitely be done in O(n) time . Take 2 pointers : one pointing to the start of the array and the second pointing to the end of the array. If sum of these 2 is less than the required sum, increment the first pointer else increment the second pointer .Iterate till u get the sum. I hope its clear now. The same has been pointed out by Sunny.
On Tue, Jun 28, 2011 at 6:29 AM, sunny agrawal <sunny816.i...@gmail.com> wrote: > 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 <sachindr...@gmail.com> > wrote: >> >> @sagar : oops ! No need of sorting. Thank you for pointing out :) >> >> On Tue, Jun 28, 2011 at 6:41 PM, sagar pareek <sagarpar...@gmail.com> >> 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 <sachindr...@gmail.com> >>> 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 <sachindr...@gmail.com> >>>> 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 <nitishgarg1...@gmail.com> >>>>> 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 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. >>>>> >>>>> >>>>> >>>>> -- >>>>> 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 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. >>> >>> >>> >>> -- >>> 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 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. >> >> >> >> -- >> 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 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. > > > > -- > 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 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. > -- 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.
