Pair sum queries (unsolved problem)

Правка en2, от Noam527, 2017-08-27 17:59:55

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.

Теги arrays, queries

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Noam527 2017-08-27 18:30:38 4
en2 Английский Noam527 2017-08-27 17:59:55 10 Tiny change: 'rmine any bounds, but the' -> 'rmine any limits, but the'
en1 Английский Noam527 2017-08-27 17:58:33 816 Initial revision (published)