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 < [email protected]> 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 < > [email protected]> wrote: > >> Are the linked list sorted? >> >> >> On 14 December 2010 05:33, divya <[email protected]> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[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]<algogeeks%[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.
