# UVA Problem: 1152 (4 Values whose Sum is 0)

**Problem Explanation:**

The main concern of this problem is to develop a fast algorithm. The O(n^4) or O(n^3) algorithm is not enough to pass the time limit. So we need a O((n^2)lg(n)) algorithm.

Ok, Here is my O(n^2lg(n)) 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 Here complexity is O(n^2 lg(n^2)) which is mathmatically O(n^2 lg(n)).
And the overall complexity of above program is O(n^2 lg(n)). You can speed up program run time by some
modification. But the overall complexity is remain same.

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.

please post sample code?

I think it will be not wise to post full source code here. You saw i already provided most part of the code in the post. You just need to combine 4 array to 2 array and then just do binary search.