Given 4 arrays, find number of quadruples having zero sum

Question

Given 4 arrays that can contain positive and negative numbers.
find all possible sets with one number from each array (ie each set will contain 4 numbers ) such that sum of 4 numbers is zero.

you can brute force it, but that's slow. Just an initial thought — Kevin, Mar 19 '12 at 16:58
Here is an [answer to similar question](http://stackoverflow.com/a/8926458/1009831), which shows how to solve this in O(n^2*log(n)) or even in O(n^2) time. — Evgeny Kluev, Mar 19 '12 at 17:16
Python brute force: `sum(not sum(tup) for tup in itertools.product(*arrays))` — Katriel, Mar 19 '12 at 17:17

Adrian · Answer 1 · 2012-03-19T17:40:36.863

Loop through array 1 and add all elements to a map.

Now from the other 3 arrays find all combinations which add up to a number in the map which you got from array 1. It's pretty straight forward. Let me know if you need some pseudocode. O(n^3) runtime

The better solution is to group arrays 2 by 2 and to do sum on those. You can generalize it to n arrays (where n is even). You are building a tree structure where each node is an array. The leaves are the initial given arrays, then one level up, you have the addition of 2 array (from the leaves), and so on. nlogn runtime, where n is the average size of the arrays. (for each elementS @position i [in the arrays] you build a tree)

EDIT: Just a note (for historical reasons)
I remember I was once had a similar question. What I did then was to still use this binary tree method but I computed combinations at each stage of the tree. I took 2 arrays and combined them into one larger array of size n^2. Then at the next stage the size of the new array was n^4 and so on. When I was left with 2 arrays I mapped one. Then just checked if elements in the other array were in the map.

+1 For a good idea: I stole your answer, modified it and posted it as my own ;-) — Gunther Piez, Mar 19 '12 at 17:20

aelguindy · Answer 2 · 2012-03-19T17:21:42.057

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

If you want to count them however, this can be solved in O(n^2 log n) and O(n^2) space by a meet-in-the-middle trick.

Let's call the arrays A, B, C, D. We create two arrays X and Y.

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

Same thing for Y with C and D. You sort X and Y (in O(n^2 log n)). Then you do:

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

score 2 · Accepted Answer · answered Mar 19 '12 at 17:19

2

Adrian just hasn't thought far enough :-)

Loop through array 1 and 2 and add all sums to a map.

Now from the other 2 arrays find all combinations which add up to a number in the map which you got from array 1 and 2. It's pretty straight forward. Let me know if you need some pseudocode.

O(n^2) runtime

answered Mar 19 '12 at 17:19

Gunther Piez

29,760
6
71
103

The solution is right, but the complexity is not. What is that magical map you use that gives O(1) access? – ElKamina Mar 19 '12 at 17:41
1

@ElKamina A hash table. The access depends on the length of the key (in this case a integer), not the size of the hash. Even an array like `bool big[maxsum]` would be sufficient. But admitted, I just copied Adrians answer and swapped some numbers. – Gunther Piez Mar 19 '12 at 18:44
Hash table never guarantees O(1) unless you can afford extra super O(n) space. Read the wikipedia article on hash based structures. The worst case complexity for hash tables is O(n), but you can bring it down to O(logn) if you use hash trees. – ElKamina Mar 19 '12 at 20:57
@ElKamina You just got it the wrong way around: If I have O(n) space, a hash table guarantees O(1) access. A simple array which is big enough to hold the maximum sum of two numbers as array guarantees O(1) access, and if you organize it bitwise hashing all 2^32 ints would even be possible on a cell phone. So of course I can afford the space, especially if I want to do something fast and invest space to gain speed. – Gunther Piez Mar 20 '12 at 00:35
That is assuming you got the perfect hashing function, which will *never* bucket two different values to the same cell. Assuming as true "bucketing at random" scenario your complexity is log(n). – ElKamina Mar 20 '12 at 00:39
You should talk to the guys who did implement `std::unordered_map`, because it has O(1) access time. They are clearly violating your rules. But honestly, O(log(n)) only if you use a tree structure (like `std::map` internally does) - which is not needed here. – Gunther Piez Mar 20 '12 at 00:51

score 1 · Answer 4 · answered Mar 19 '12 at 17:08

Brute Force Method: NOTE I HAVEN'T TESTED 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);
                        }
                    }
                }
            }
        }
    }

IntegerSet class

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

this is O(n4) solution....there must be some elegant solution....looking for that — MoveFast, Mar 19 '12 at 17:15
Funny sorting of i,j,k,l. How would you do it with 100 arrays? — user unknown, Apr 09 '12 at 07:24

ElKamina · Answer 5 · 2012-03-19T17:39:50.080

1

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

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

edited Mar 19 '12 at 17:39

answered Mar 19 '12 at 17:19

ElKamina

7,747
28
43

I think you mean O(n^2 log n) – aelguindy Mar 19 '12 at 17:22
Its complexity is O(n2 * log (n) ) – MoveFast Mar 19 '12 at 17:24

Given 4 arrays, find number of quadruples having zero sum

5 Answers5