Algorithm for sum-up to 0 from 4 set

Question

I have 4 arrays A, B, C, D of size n. n is at most 4000. The elements of each array are 30 bit (positive/negative) numbers. I want to know the number of ways, A[i]+B[j]+C[k]+D[l] = 0 can be formed where 0 <= i,j,k,l < n.

The best algorithm I derived is O(n^2 lg n), is there a faster algorithm?

Answer 1

Ok, Here is my O(n^2lg(n^2)) algorithm-

Suppose there is four array A[], B[], C[], D[]. we want to find the number of way A[i]+B[j]+C[k]+D[l] = 0 can be made where 0 <= i,j,k,l < n.

So sum up all possible arrangement of A[] and B[] and place them in another array E[] that contain n*n number of element.

int k=0;
for(i=0;i<n;i++)
{
    for(j=0;j<n;j++)
    {

        E[k++]=A[i]+B[j];


    }
}

The complexity of above code is O(n^2).

Do the same thing for C[] and D[].

int l=0;

for(i=0;i<n;i++)
{
     for(j=0;j<n;j++)
     {

          AUX[l++]=C[i]+D[j];

     }
}

The complexity of above code is O(n^2).

Now sort AUX[] so that you can find the number of occurrence of unique element in AUX[] easily.

Sorting complexity of AUX[] is O(n^2 lg(n^2)).

now declare a structure-

struct myHash
{
  int value;
  int valueOccuredNumberOfTimes; 

}F[];

Now in structure F[] place the unique element of AUX[] and number of time they appeared.

It's complexity is O(n^2)

possibleQuardtupple=0;

Now for each item of E[], do the following

for(i=0;i<k;i++)
 {

     x=E[i];

     find -x in structure F[] using binary search.
     if(found in j'th position)
     {
        possibleQuardtupple+=number of occurrences of -x in F[j];

     }      
 }

For loop i ,total n^2 number of iteration is performed and in each iteration for binary search lg(n^2) comparison is done. So overall complexity is O(n^2 lg(n^2)).

The number of way 0 can be reached is = possibleQuardtupple.

Now you can use stl map/ binary search. But stl map is slow, so its better to use binary search.

Hope my explanation is clear enough to understand.