5 numbers such that their sum is 0

Question

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

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

Is it possible to solve this problem with complexity better than O (n ^ 2 + n ^ 3) (using a hash map)?

Answer 1

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

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

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

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