#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

#### Categories

Welcome to the new platform of Programmers Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use it's exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

# Finding 2 numbers in a set that add up to n

Posts: 1Member
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?
· ·

• Posts: 54Member
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.
· ·
• Posts: 1Member
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.
· ·
• Posts: 4Member
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 :D)
· ·
• Posts: 4Member
This post has been deleted.
· ·