Author |
Topic: two members sum in hash table question (Read 1381 times) |
|
transgalactic
Newbie
Posts: 11
|
 |
two members sum in hash table question
« on: Jan 15th, 2012, 7:15am » |
 Quote  Modify
|
there is a set S which consists of n numbers.
and another number Z
write an algorithm which checks if there are
two different members in S which sum is Z.
it should be done in avarage time of
theta(n)
??
i thought of using the chaining method of hashing
to store our set S
(creating linked list in case of colitions)
so in this case we will have theta(1+alfa) to search for some member.
so for each member in the hashe table i can use the search method to find the
z-S[i] member.(in linear loop)
and
does
my solution correct?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: two members sum in hash table question
« Reply #1 on: Jan 15th, 2012, 9:58am » |
Quote Modify
|
If S is sorted, you could just put pointers at both ends, and increase the left pointer if the two elements pointed to sum to a value less than Z and decrease the right pointer if it's greater.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
transgalactic
Newbie
Posts: 11
|
|
Re: two members sum in hash table question
« Reply #2 on: Jan 15th, 2012, 11:52am » |
Quote Modify
|
its not sorted
what about my solution with the hash table
?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print