Given 4 arrays, find the number of quadruples with zero sum

Question

• 4 arrays are provided that can contain positive and negative numbers.
• find all possible sets with one number from each array (i.e. each set will contain 4 numbers), so that the sum of 4 numbers is zero.

Answer 1

Adrian just did not think far enough :-)

Scroll array 1 and 2 and add all the amounts to the card.

Now, from the remaining 2 arrays, they find all the combinations that add to the number on the map that you received from array 1 and 2. This is pretty straight forward. Let me know if you need pseudo code.

O (n ^ 2) runtime

Answer 2

Scroll array 1 and add all the elements to the map.

Now, from the remaining 3 arrays, they find all combinations that add to the number on the map that you got from array 1. This is pretty straight forward. Let me know if you need pseudo code. O (n ^ 3) runtime

The best solution is to group 2 by 2 arrays and do the sum on them. You can generalize it to n arrays (where n is equal). You are building a tree structure where each node is an array. Leaves are the initial given arrays, then one level up, you have the addition of 2 arrays (from leaves), etc. nlogn , where n is the average size of the arrays. (for each element of S @position i [in arrays] you create a tree)

EDIT: Just a note (for historical reasons)
I remember I had the same question. What I did then was to use this binary tree method, but I calculated the combinations at each stage of the tree. I took 2 arrays and combined them into one larger array of size n ^ 2. Then, in the next step, the size of the new array was n ^ 4, etc. When I have 2 arrays left, I matched them. Then just check if the elements are in another array on the map.

Answer 3

If you want to find all of them, there is no way in o (n ^ 4) to do this, since there can be so many sets.

If you want to calculate them, this can be solved in the spaces O (n ^ 2 log n) and O (n ^ 2) using the “in the middle” trick.

Call arrays A, B, C, D. Create two arrays X and Y.

for a in A: for b in B: X.append(a + b) 

Same goes for Y with C and D. You sort X and Y (in O (n ^ 2 log n)). Then follow these steps:

 i = 0 j = size(Y) - 1 count = 0 while i < size(X) and j >= 0: if X[i] + Y[j] == 0: ii = 1 jj = 1 while X[i] == X[i + 1]: ii++ i++ while Y[j] == Y[j - 1]: jj++ j-- count += ii * jj if X[i] + Y[j] > 0: j-- if X[i] + Y[j] < 0: i++ Output count 

Answer 4

Brute Force Method: NOTE I DID NOT TEST THIS

 public void setsOfZero(int[] one,int[] two,int[] three,int[] four) { List<IntegerSet> setsOfIntegers = new ArrayList<IntegerSet>(); for(int i =0;i < one.length ; i++) { for(int k = 0; k < two.length; k++) { for(int j = 0; j<three.length; j++) { for(int l = 0;l< four.length; l++) { if((one[i]+ two[k] + three[j] + four[l])==0) { IntegerSet intSet = new IntegerSet(); intSet.one = one[i]; intSet.two = two[k]; intSet.three = three[j]; intSet.four = four[l]; setsOfIntegers.add(intSet); } } } } } } 

Class IntegerSet

 public class IntegerSet{ public int one =0; public int two =0; public int three =0; public int four =0; } 

Answer 5

Take the first two arrays (A, B) and create a new array (E) with pairwise sums. Pair array sorting (E). For each pair of numbers in the remaining two arrays (C, D), check if their compliment exists in the pair array (E).

Difficulty: O (n ^ 2 log (n))