Find if a sum of any two elements is set S is equal to given x in nlgn - Programmers Heaven

Howdy, Stranger!

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


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.

Find if a sum of any two elements is set S is equal to given x in nlgn

I got a little problem with this excercise from Introduction to Algorithms (Cormen et al.).

Given a set S of n integers, and an integer x, describe an algorithm of time complexity n*lg(n) which finds if sum of any two elements from S are equal to x.

Examining every pair gives n*n algorithm, which is not what I want.
I think a merge-sort like algorithm could be used, but have no idea how to check if there are two such elements in two subsets (the merge step) in linear time. But maybe the whole idea is wrong. If someone can give any hints on this, I'd appreciate it =)

Oh. My second idea is a 2*n*lg(n) algorithm given below.

merge-sort(S) // takes n*lg(n)
for each y in S: // n times
r = x - y
binary-search(S, r) // takes at most lg(n)
if found then return

If anyone knows a better (faster) solution please let me know.

Sign In or Register to comment.