we can use binary search algorithm to find the "z" ( sorting ll take O(n log n ) but it is very less compared to n^2 * log n )
-- Prashant Kulkarni On Wed, Dec 15, 2010 at 3:32 PM, Ankur Murarka <ankur.murarka....@gmail.com>wrote: > wouldn't your algo take n^3 time as well given the fact that the lists are > not sorted? searching for the matching value fr z should be taking O(n) time > and to do so for each pair of x and y shall take O(n^2). > Please correct me if i got something wrong here > > On Wed, Dec 15, 2010 at 11:44 AM, Prashant Kulkarni < > prashant.r.k...@gmail.com> wrote: > >> Hi, >> Very good question. >> >> i think very knows brute-force soln of n^3 time complexity. >> >> here is a alternative method/soln of O(n^2 * log(n)) time complexity Algo >> >> 1) pick any number from list A (One by one)...... let say 'x' >> >> 2) pick any number from list B (one by one )...... let say 'y' >> >> 3) z=x+y >> >> 4)look for 'z' in the list by considering all numbers as unsigned if u >> found then check sign of that number it be opposite of 'z' if so return 1 >> else 0 >> >> [above steps is repeated for all elements] >> >> *correct me if I am wrong* >> >> -- >> Prashant Kulkarni >> IISc Bangalore >> >> >> >> >> On Wed, Dec 15, 2010 at 10:36 AM, Soumya Prasad Ukil < >> ukil.sou...@gmail.com> wrote: >> >>> Are the linked list sorted? >>> >>> >>> On 14 December 2010 05:33, divya <sweetdivya....@gmail.com> wrote: >>> >>>> Given three lists: A, B and C of length n each. Write a function which >>>> returns true if any 3 three numbers (1 from each list), sum up to >>>> zero. Else return false, if there is no such combination. >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To post to this group, send email to algoge...@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>> . >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>>> >>> >>> >>> -- >>> regards, >>> soumya prasad ukil >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
