sort array c only. now select every pair from array a nd b ( o(n2)) for every pair find the element from c which gives sum of the three element 0. ( search using binary search as c is sorted) so the algo is O (n^2 logn))
On 16 June 2010 13:47, Amir hossein Shahriari < [email protected]> wrote: > @algoose chase: you're right thx for the test case > > On Wed, Jun 16, 2010 at 11:45 AM, Algoose Chase <[email protected]>wrote: > >> @ Amir: >> I think you cannot find two numbers in B and C such that their sum is >> -A[k] in O(n) in all cases with the logic that you mentioned. >> >> for instance you can try with : >> A : 2 7 8 10 >> B :-2, 0, 1, 9 >> C: -7 -2 1 3 >> >> On Wed, Jun 16, 2010 at 5:56 AM, Amir hossein Shahriari < >> [email protected]> wrote: >> >>> sort all arrays >>> for each number in A , A[k] >>> find two numbers in B and C such that their sum is -A[k] >>> this can be done in O(n) time: >>> >>> set i at the beginning of B and j at the end of C >>> while i<n or j>=0 >>> if ( B[i] + C[j] == -A[k] ) return true >>> if ( B[i] + C[j] < -A[k] ) increase i >>> else decrease j >>> >>> we have to do this for each element of A so the overall complexity is: >>> O(n2) time O(1) space >>> >>> correct me if I'm wrong >>> >>> On 6/15/10, sharad kumar <[email protected]> wrote: >>> > plzzz comment on this question >>> > >>> > -- >>> > 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]<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.
