Summation algorithm up to 0 out of 4 sets

Question

I have 4 arrays of A , B , C , D size n . n not more than 4000. 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 obtained is O(n^2 lg n) , is there a faster algorithm?

Answer 1

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

Suppose that there are four arrays A [], B [], C [], D []. we want to find the number of paths A [i] + B [j] + C [k] + D [l] = 0, where 0 <= i, j, k, l <n.

So, we summarize all the possible locations of A [] and B [] and put them in another array E [], which contain n * n number of elements.

 int k=0; for(i=0;i<n;i++) { for(j=0;j<n;j++) { E[k++]=A[i]+B[j]; } } 

Code complexity above O (n ^ 2).

Do the same 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]; } } 

Code complexity above O (n ^ 2).

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

The complexity sorting AUX [] is O (n ^ 2 log (n ^ 2)).

now declares a structure -

 struct myHash { int value; int valueOccuredNumberOfTimes; }F[]; 

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

Difficulty is O (n ^ 2)

 possibleQuardtupple=0; 

Now for each element 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 the loop, I perform the total number of iterations n ^ 2 and in each iterate for the binary search lg (n ^ 2). So overall the complexity is O (n ^ 2 log (n ^ 2)).

Number of paths reached 0: = possibly Quardtupple.

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

Hope my explanation is clear enough to understand.

Answer 2

I do not agree that your decision is actually as effective as you say. In your decision, populating E [] and AUX [] is O (N ^ 2) each, so 2.N ^ 2. Each of them has N ^ 2 elements.

Generation x = O (N)

Sort AUX = O ((2N) * log ((2N)))

The binary search of E [i] in AUX [] is based on the elements N ^ 2, which can be found in the elements N ^ 2.

So you are still doing the N ^ 4 job, as well as the extra work generating intermediate ans arrays for sorting the N ^ 2 elements in AUX [].

I have a solution (work continues), but it is very difficult for me to calculate how much this works. I deleted my previous answer. I will send something when I am more confident in myself.

I need to find a way to compare O (X) + O (Z) + O (X ^ 3) + O (X ^ 2) + O (Z ^ 3) + O (Z ^ 2) + X.log (X) + Z.log (Z) - O (N ^ 4), where X + Z = N.

This is clearly less than O (N ^ 4) ... but how much ???? My math fails here.

Answer 3

The judgment is incorrect. The supplied solution generates arrays of size N ^ 2. Then it works with these arrays (sorting, etc.).

Therefore, the order of the work, which would be normal O (n ^ 2.log (n)), should have n replaced by n ^ 2. Thus, the result is O ((n ^ 2) ^ 2.log (n ^ 2) )