In O(n^2). Sort two of the arrays, say B and C, into ascending order. For each element in A, search forward in B and backwards in C looking for a zero sum. Something like this, using zero-based arrays of length n:
int i, j, k; for( i = 0 ; i < n ; ++i ) { j = 0; k = n-1; while( (j < n) && (k >= 0) ) { if( a[i] + b[j] + c[k] < 0 ) j++; else if( a[i] + b[j] + c[k] > 0 ) k--; else return TRUE; } } return FALSE; The two sorts are O(n log n). The while loop executes at most 2n times for each value of i. So the for loop is O(n^2). Dave On Feb 17, 12:08 pm, bittu <shashank7andr...@gmail.com> 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 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.