I came up with the following problem a few days ago and I didn't manage to solve it in a better complexity than O(NlgN + QN), maybe you can help as I'm stuck and starting to think it's impossible:

You're given an array of N elements, and Q queries. Each query consists of a single integer X, and you're asked to determine if there's a pair of integers in the array whose sum is X, or if there isn't any.

I didn't determine any limits, but the less, the better. some bounds can be on the maximal value of an element in the array, I don't mind, as long as someone finds a solution better than mentioned earlier. Would also be better if the algorithms will be able to output the indicies of the 2 integers with sum X.

I'd also be happy if someone proves it to be impossible.

Auto comment: topic has been updated by Noam527 (previous revision, new revision, compare).If

Ais an upper bound for elements in array, we can solve the problem in . Let's consider a polynomial whereais our array.kis sum of two elements if and only if coefficient of the termt^{k}inP^{2}is nonzero. So you can findP^{2}using FFT and handle queries inO(1).Though, this solution can't find indices of these elements.

This is excellent, thanks!

I had an idea of limiting the array values and then finding a way to compute all distinct pair sums in less than O(N^2), but I don't know FFT yet.

Thank you :) Do you think there's a solution which also outputs the indicies?

There is some solution that's probably slow in practice, but for small

Ait's asymptotically faster than trivial:Let's divide our numbers to almost equal groups and construct polynomials for each group separately.

P_{i}is a polynomial for groupi,Pis a polynomial for all numbers. Find all productsP·P_{i}using FFT.For each query we can find a pair

isuch thatP·P_{i}has a nonzero coefficient. Now let's just iterate over all numbers in i-th group and check does it fit.Overall complexity is .

If we can solve this problem in

O(N^{2 - ε}) (whenN=Q) then we can solve the 3SUM problem inO(N^{2 - ε}). Thus, a major improvement of the runtime seems impossible.I know it's pretty trivial, but if

Q»N, then it can be solved inO(N^{2}*log(N^{2}) +Q*log(N^{2})), by storing all possible sums in a vector, sorting them, and then every query you can binary search for the given sum. This can also return indices, if you store tuples instead of values in the array.