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?

Comments

  • 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 :D)
  • This post has been deleted.
Sign In or Register to comment.

Howdy, Stranger!

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

Categories