Search code examples
c++calgorithmfftconvolution

Find all differences in an array in O(nlogn) where n is the max range of elements

Question: Given a sorted array A find all possible difference of elements from A, where each element is an integer in the range [1, ..., n]. Also, you can assume there are no duplicates. So max size of the array will be <= n.

Note: Total possible differences will be in the range of [1, ..., n-1] because of the above constraints.

Example (for N=12):

Input: 1, 6, 10, 12
Output: 2, 4, 5, 6, 9, 11

The question is similar to this one, except n is the no. of elements in that question, not the upper bound of the element.

There's also an answer in the same question, this one: https://stackoverflow.com/a/8455336/2109808 This guy claims it can really be done in O(nlogn) using fft and self convolution, but I don't get it, and it also seems to be incorrect when I try it on online convolution calculators (like this one).

So, does anyone know how this can be achieved in O(nlogn)?

Thank you in advance :)

Solution

  • This answer linked by OP suggest the following steps:

    1. Assume an array with non-repeating elements in the range [0, n-1].*
    2. Create an array of length n, where elements whose index matches an element of the input are set to 1, other elements are set to 0. This can be created in O(n). For example, given in input array [1,4,5], we create an array [0,1,0,0,1,1].
    3. Compute the autocorrelation function. This can be computed by taking the FFT, squaring its magnitude, and then taking the IFFT. This is O(n log n).
    4. The output is non-zero for indices corresponding to a difference present in the input. The element at index 0 is always non-zero, and should be ignored. Finding and printing these elements is O(n).

    Note that this process is not correct, because the auto-correlation function as computed through the FFT is circular. That is, given an input array with two values, 0 and n-1, the output will have a non-zero element at index 1 as well as at index n-1. To avoid this, it would be necessary to make the array in step #2 of length 2n, leaving half of it set to 0. The second half of the output array should then be ignored. Doubling the array size doesn't change the computational complexity of the algorithm, which is still O(n log n).

    * I changed the range from that given by OP for simplicity, it is trivial to change this range by adding an offset to all indices.