5 numbers such that their sum equals 0

Question

Given 5 arrays of size n: a, b, c, d, e. How many (i, j, k, g, h) are there such that

a(i) + b(j) + c(k) + d(g) + e(h) = 0 ?

Can this problem be solved with complexity better than O(n^2 + n^3) (using hash map) ?

Answer 1

If the arrays contain integers of limited size (i.e. in range -u to u) then you can solve this in O(n+ulogu) time by using the fast Fourier transform to convolve the histograms of each collection together.

For example, the set a=[-1,2,2,2,2,3] would be represented by a histogram with values:

ha[-1] = 1
ha[2]  = 4
ha[3]  = 1

After convolving all the histograms together with the FFT, the resulting histogram will contain entries where the value for each bin tells you the number of ways of combining the numbers to get each possible total. To find the answer to your question with a total of 0, all you need to do is read the value of the histogram for bin 0.