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 <[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.
