Finding 2 numbers in a set that add up to n

Hi guys, have a question..

If given a set of numbers and a number [b]n[/b], find if there are 2 numbers in the set that add up to n. (O(n lgn) time) is optimal, n^2 is the simple answer

any ideas?

• I guess my main question and concern is:

Is the set ordered?

If it is then it's just a matter of keeping two iterators to the set on starting at the high end and one starting at the low end.

Checking the sum, if it's greater that n:
Is the high number greater than n?
If it is then move that iterator down
... check the sum ...
etc etc.

This shouldn't lead to O(n^2), but I haven't done the math on it so I'm not sure if it is the O( n lg n ) solution you are looking for.
• It is O(n lg n) even if the list is unsorted: Sort it in O(n lg n) time, then your technique for the sorted list is just O(n), so the sort is the bottleneck.
• start from first element a[i] search for sum-a[i] using binary search log(n)..iterate through all n elements
total [b]n*log(n)[/b]

(PS: I am just wondering that the solution can't be this simple )
• This post has been deleted.