Author |
Topic: 4 members of sum z in hash table (Read 1241 times) |
|
transgalactic
Newbie
Posts: 11
|
 |
4 members of sum z in hash table
« on: Jan 15th, 2012, 7:22am » |
 Quote  Modify
|
i have a set S of n members and a number Z
i need to find 4 different members which sum is Z
and the time complexity is theta(n^2)
?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: 4 members of sum z in hash table
« Reply #1 on: Jan 15th, 2012, 10:02am » |
Quote Modify
|
Use a hashmap mapping A*B A+B to the pair (A,B)
Then for each A*B A+B in the table find Z/(A*B) =C*D Z-(A+B) =C+D and see if A,B,C and D are distinct.
i.e. same thing as http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs; action=display;num=1325343356 but using a hash-table.
|
| « Last Edit: Jan 15th, 2012, 12:35pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
transgalactic
Newbie
Posts: 11
|
|
Re: 4 members of sum z in hash table
« Reply #2 on: Jan 15th, 2012, 11:59am » |
Quote Modify
|
i cant understand the meaning of
"Use a hashmap mapping A*B to the pair (A,B)"
you want me to create all the combinations of
multiplications via double loop.
then you want me o hash them
what does the function pair(A,B) does?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 4 members of sum z in hash table
« Reply #3 on: Jan 15th, 2012, 12:34pm » |
Quote Modify
|
Oh wait, I seem to have misread somewhere, you want to sum, not multiply.
Well, anyway. You want distinct numbers, right. So you need to find two pairs of numbers that sum to Z: i.e. (A+B) + (C+D) = Z
By using a hashtable that maps A+B back to the pair of numbers A and B, you can iterate over the n*(n-1)/2 sums of two numbers, and find which pair of numbers give that sum, that way you can check all four are distinct.
|
| « Last Edit: Jan 15th, 2012, 12:36pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print