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 anyboundlimits, 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.
↵
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
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.
