Bit Manipulation AdHoc Variation

Question

Question:

You are given two sorted arrays A and B (size can vary from 1 to 10^5), having elements in range of (1,10^5). You are also given an array C of size Highest element in A + Highest element in B, with all elements 0 initially. Now, we have to update C like this:

for i in A:
    for j in B:
        C[i+j] += 1

And have to find out final C.

Time Limit: 1sec (So Time Complexity should not be n^2)

Example:

A = [2,4]
B = [1,3]
Then C would be = [0,0,1,0,2,0,1] (assuming 1th indexed)

I am not sure from where I should start. I tried to think a way so that we could increase more than 1 in C at a time, But could not find it. For a moment I was thinking in this way, Assume A as binary string: "0101" and we are shifting It by elements in B, But again this is not leading anywhere too.

Any help would be appreciated. Thanks.

Answer 1

If you think of your initial arrays as a histogram, then the output is given as a convolution of the two input histograms.

You can use the fast fourier transform to perform this convolution in O(nlogn) time.

For example, in Python:

import scipy.signal

def hist(X):
    """Prepare a histogram of X"""
    h = [0]*(max(X)+1)
    for x in X:
        h[x] += 1
    return h

A = [2,4]
B = [1,3]
print scipy.signal.fftconvolve(hist(A),hist(B))

With arrays of length 10^5, this only takes 0.05 seconds on my computer.