Noam527's blog

Pair sum queries (now solved problem)
By Noam527, history, 7 years ago, In English

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.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +22 Vote: I do not like it

If A is an upper bound for elements in array, we can solve the problem in . Let's consider a polynomial where a is our array. k is sum of two elements if and only if coefficient of the term tk in P2 is nonzero. So you can find P2 using FFT and handle queries in O(1).

Though, this solution can't find indices of these elements.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There is some solution that's probably slow in practice, but for small A it's asymptotically faster than trivial:

      Let's divide our numbers to almost equal groups and construct polynomials for each group separately. Pi is a polynomial for group i, P is a polynomial for all numbers. Find all products P·Pi using FFT.

      For each query we can find a pair i such that P·Pi has a nonzero coefficient. Now let's just iterate over all numbers in i-th group and check does it fit.

      Overall complexity is .

      → Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

If we can solve this problem in O(N2 - ε) (when N = Q) then we can solve the 3SUM problem in O(N2 - ε). Thus, a major improvement of the runtime seems impossible.

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I know it's pretty trivial, but if Q»N, then it can be solved in O(N2 * log(N2) + Q * log(N2)), 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.

→ Reply