-1

Possible Duplicate:
Determine whether or not there exist two elements in Set S whose sum is exactly x - correct solution?

Consider an unsorted array of numbers and an constant Z. We want to find whether there are two elements in the array whose sum is Z.

I know there is an O(n*lgn) algorithm to do so. But is there an algorithm that run in O(n) average case?

Community
  • 1
  • 1
spider
  • 53
  • 5
  • This question has been answered numerous times. Do some search (or just search) before posting. See: http://stackoverflow.com/questions/2171969/determine-whether-or-not-there-exist-two-elements-in-set-s-whose-sum-is-exactly – ElKamina Feb 22 '12 at 01:09
  • This looks like homework, the same question was asked yesterday http://stackoverflow.com/questions/9373450/choose-k-items-from-a-set-of-x-and-y-to-meet-certain-criteria/9374185#9374185 – Rusty Rob Feb 22 '12 at 01:32
  • @ElKamina This question is about an O(n*log(n)) algorithm, and all of the proposed solutions run in Θ(n*log(n)) on average. Neither what you proposed as a duplicate, nor the other questions I find in a cursory search, discuss the possibility of an O(n) algorithm. – Gilles 'SO- stop being evil' Feb 23 '12 at 15:17
  • @Gilles actually there were several 0(n) solutions offered. Including http://stackoverflow.com/a/2172045/14167. – David Nehme Mar 05 '12 at 00:53
  • @DavidNehme I don't see any. The one you cite is not O(n). It performs Θ(n) hash table lookups, and hash table lookups are at best O(lg(n)). This is amply explained in the comments below the answer. – Gilles 'SO- stop being evil' Mar 05 '12 at 09:29

1 Answers1

0

Well, after some thinking, I come up with the following scheme:

  1. make a hash table of size 2n
  2. for each value s in S, hash both s and Z-s into the hash table
  3. if there is a collision, then there exists 2 element whose sum is equal to Z

this scheme has a running time of O(n).

Johannes Weiss
  • 52,533
  • 16
  • 102
  • 136
spider
  • 53
  • 5