Here is an O(N^2) algorithm:
1. Sort both A and B. (O(NlogN) or O(N^2), either will work)
2. For each element C[k] in C, find if there is such (i,j) pair that
A[i] + B[j] = -C[k]:
Start with i = 0 and j = N-1, and loop through the following:
a. if A[i] + B[j] > -C[k], then j = j-1;
b. if A[i] + B[j] < -C[k], then i = i+1;
c. if A[i] + B[j] = -C[k], then combination A[i]+B[j]+C[k]=0 is found.
If i or j goes beyond the valid range in case a or b, then no such
combination.
The table A[i] + B[j] (i, j=0,1,...,N-1) actually forms an (implicit)
Young Tableau.
See http://en.wikipedia.org/wiki/Young_tableau
and
http://placementsindia.blogspot.com/2008/05/search-in-young-tableau-sorted-matrix.html
On 2010-12-14 21:33, divya 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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
