Here are two methods to do in O(n^2) 1) Insert elements of first array in hash and then for every pair of elements in (Bj, Ck) find if -(Bj + Ck) is in hash
2) Without extra space: sort arrays A and B now for each element in Ck find a pair (Ai, Bj) which sums to -Ck as below let p1 point to first element in A let p2 point to last element in B if p1 + p2 < -Ck move p1 one step to right if p1 + p2 > -Ck move p2 one step left if ( p1 + p2 == -Ck ) return triplet Thanks, Balaji. On Thu, Feb 17, 2011 at 11:42 PM, jalaj jaiswal <[email protected]>wrote: > i have a n^2logn solution > > sort the third array,.. then for every pair in a and b search for the > number which makes the sum zero using binary search > > > but guess a better soln must exist > > > On Thu, Feb 17, 2011 at 11:38 PM, bittu <[email protected]>wrote: > >> We have three arrays >> A=[a1,a2,...an] >> B=[b1,b2,...bn] >> C=[c1,c2,...cn] >> >> Write a method which takes these three arrays as input and return true >> if there is a combination [ai,bj,ck] such that ai+bj+ck = 0. >> >> O(n^3) solution is obvious. The questions is can we do better than >> this? >> >> >> >> >> >> >> >> >> >> >> >> Thanks & Regards >> Shashank Mani >> >> -- >> 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. >> >> > > > -- > With Regards, > *Jalaj Jaiswal* (+919019947895) > Software developer, Cisco Systems > B.Tech IIIT 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. > -- 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.
