Author |
Topic: algorithm of finding different members (Read 1439 times) |
|
transgalactic
Newbie
Posts: 11
|
 |
algorithm of finding different members
« on: Dec 31st, 2011, 6:55am » |
 Quote  Modify
|
suppose that there is a set S of n whoule numbers.
and another whole number Z.
suppose that all the members in the group S are from the range [0..n^k -1]
A)
write an algorithm that finds if there are 4 members in S which differ each other and their sum is Z.
the time complexity of the algorithm shoud be
theta(n^2 min(k,lg n))
?
B)
its the same as A but we need to find 5 such numbers
which differ one another and the sum of these 5 numbers is Z and with time complexity theta(n^3)
?
i think it uses radix sort
am not sure
any guidance willl be apriciated
thanks
|
| « Last Edit: Dec 31st, 2011, 9:35am by transgalactic » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: algorithm of finding different members
« Reply #1 on: Jan 1st, 2012, 6:40am » |
Quote Modify
|
A) Take the unique pairs of different numbers from S, and sort them on their sum, then start at front and end of those ordered pairs and find two pairs that have different numbers and sum to Z.
B) For each number X in S find 4 that sum to Z-X as above.
|
| « Last Edit: Jan 1st, 2012, 6:42am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
transgalactic
Newbie
Posts: 11
|
|
Re: algorithm of finding different members
« Reply #2 on: Jan 2nd, 2012, 2:58am » |
Quote Modify
|
regarding part A:
ok i will take unique pairs. i will sum them together
and then i will sum the "sums".
and i will look for Z amongst these sums.
but the problem is proving that this algoritm works on
theta(n^2 min(k,lg n))
time complexity.
and another problem is how to know if amongst the two sums there isnt the same member in each pair.
?
if i will try to translate your words into psedo code.
A-is the input array of size n
B- is additional array with size n/2
for i<- 1 to n
for j<- 1 to n
if A[i] differs A[j]
do B[floor(i/2)]<- A[i]+A[j]
for i<- 1 to n
for j<- 1 to n
if B[i]+B[j]=z
do print "there is such 4 numbers"
nut as you see its time complexity of n^2
not what they asked in the question
|
|
IP Logged |
|
|
|
transgalactic
Newbie
Posts: 11
|
|
Re: algorithm of finding different members
« Reply #3 on: Jan 2nd, 2012, 3:11am » |
Quote Modify
|
this question on the subject of
radix sord ,bucket sort ,conting sort
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print