Finding 2 numbers in a set that add up to n - Programmers Heaven

Howdy, Stranger!

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

Categories

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.