Howdy, Stranger!

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

Sign In with Facebook Sign In with Google Sign In with OpenID

Categories

We have migrated to a new platform! Please note that you will need to reset your password to log in (your credentials are still in-tact though). Please contact lee@programmersheaven.com if you have questions.
Welcome to the new platform of Programmer's 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 its 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

pouncerpouncer 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?

Comments

  • nebgastnebgast 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.
  • aisthesisaisthesis 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.
  • nunnajaikishnunnajaikish 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)
  • nunnajaikishnunnajaikish Posts: 4Member
    This post has been deleted.
Sign In or Register to comment.