Asymptotically optimal way to find the sum of three elements of an array closest to a given number

Question

In his answer to this question, John Feminella says:

It's possible to do this sub-quadratically if you get really fancy, by representing each integer as a bit vector and performing a fast Fourier transform, but that's beyond the scope of this answer.

What is the asymptotically optimal way of solving the problem described in that question?

Brenza

Answer 1

Suppose we have an array 1 2 4. We represent this array as a polynomial f(x) = x^1 + x^2 + x^4. Let's look at f(x)^2, which is

x^2 + 2 x^3 + x^4 + 2 x^5 + 2 x^6 + x^8

The number of ways to write n as the sum of two elements of the array is the coefficient of x^n, and this is true in general. FFT gives us a way to multiply polynomials efficiently*, so basically what we do is compute f(x)^3 and look at the coefficient of the target number S.

• The reason this algorithm doesn't solve the 3SUM problem is that the efficiency of an FFT multiply depends on the degree of the resulting polynomial and thus that the array values lie in a small range.

Acrefoot

f(x)^3 has O(n^3) coefficients. Will the FFT allow you to compute a useful subset of the coefficients? – Furlani

It seems like this would detect whether three numbers summed to a given target, but it wouldn't find what those three numbers are. Am I mistaken about this? – Bobker

@Tom It's only a win when the range is small and thus f(x)^3 has degree <<< n^2. – Acrefoot

@Bobker You're right. It's possible to call this as a subroutine O(log n) times to figure out what the numbers are. – Acrefoot

@foo- How exactly would you do this? I don't see what these calls would look like. – Bobker

@Bobker A simple randomized strategy would be to try subsequences where each element is included independently with probability 1/2. The three target elements are all included with constant probability, and in expectation a constant fraction of the others go away. I'm confident this can be derandomized but don't have a cite offhand. – Acrefoot

@Bobker See this on how to recover the solution. cstheory.stackexchange.com/questions/32036/… – Founder