This link shows the following algorithm that uses FFT to find differences of all pairs in an array.
Assume an array with non-repeating elements in the range [0, n-1].
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].
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).
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).
Can anyone explain how is this working or prove that it gives correct answer.
It looks like it is using the algorithm of finding pairwise sum using FFT.
