Welcome, %1$s. Please login or register.

February 21, 2018, 05:11:11 PM
: 1
: How many calls?  ( 6331 )
« : June 22, 2007, 03:41:43 PM From Prateek»



How many calls?


There is a group of N people, with each person having some unique information with him/her. These N people want to share all the information they have among themselves using phone calls. Whenever two persons talk to each other over the phone, they share all the information that they currently possess.

What is the minimum number of phone calls required to accomplish this task?
Do justify your answer.

 
Liked It? Share it!

              


« #1 : June 22, 2007, 09:16:05 PM From PSM»

i think the answer is (2N-3) no. of calls has to be made so that each one can have every information.....
their r N people..1st person will call every one of them one by one..
first call he will make to 2nd person .after this call 1st person will have information of 2nd also similarly2nd will have the information of the 1st...
now second call will be made by 1st person will be to 3rd person...
afetr this talk 1st will have information of all three... and 3rd person will also have information of all three...
similarly this will keep on gng till the 1st per makes call to the Nth person.....(N-1 calls have been taken place)
now before this last call 1st person was having information of all the person from 1 to N-1...
and after this talk he will have information of all N persons.... also the Nth person will also have information of all the N persons..
now again 1st person will call all the remaining N-2 persons....and give them the remaining information......making N-2 calls this time

total calls he made =N-1+N-2= 2N-3

i hope it to be right well plzzz reply is it is right or wrong..
« #2 : June 23, 2007, 11:43:07 AM From Prateek»

There is a shorter way of doing it.  :-\
« #3 : June 30, 2007, 06:19:04 PM From preep»

(NC2)/2 i think...
« #4 : August 09, 2007, 12:33:20 PM From eisenham»

 I think the ans is (N-1). The first will call the next and then share his info. The second will call next and share the info of first and second. And so on.
« #5 : August 09, 2007, 01:31:29 PM From Prateek»

Since this is a tricky problem to generalise, lets take a smaller case of it.
How many calls are required if there are 4 people and they all should share information with the rest 3?
« #6 : August 10, 2007, 03:18:43 PM From eisenham»

The answer is (2N-3).  For 4 people it will require 5 calls.

call                              Info with caller ater the call

1 -->2                       1,2
2 -->3                       1,2,3
3 -->4                       1,2,3,4
4                              1,2,3,4
3 -->2                       1,2,3,4
2 -->1                       1,2,3,4   
« #7 : August 10, 2007, 07:12:13 PM From Prateek»

For 4 people the number of calls required is not 5. It is lesser.
« #8 : August 13, 2007, 03:06:39 PM From eisenham»

for 4 people answer is 4.

call             Info with caller ater the call

1-->2          1,2
3-->4          3,4
2-->3          1,2,3,4
1-->4          1,2,3,4

can it be done lesser than this ?
       
« #9 : August 14, 2007, 02:38:38 PM From Prateek»

Yeah, 4 is the right answer for 4 people. Can anyone generalize now?  ::)
« #10 : August 14, 2007, 06:54:38 PM From atul»

Should be 2N - 4

a) One person calls the N-4 people successively in group and gets all info from them
b) 4 people (This person with remaining 3) make 4 calls and have all the info among them
c) One of these makes N-4 to the original N-4 people and everyone has all info

« #11 : August 14, 2007, 07:00:19 PM From atul»

Food for thought:

here we see that 4 is the magic unit of optimization and that is the only optimization which we can do in tthe question. Let me explain this with 5 people one of easiest method is
X calls W, Y and Z in last
Z and X has all info. X calls W and Y

So 5 is worst and 4 is the best !!

Even if there are N people worst is X calls N-1 and then N-2 again i.e. 2N-3 which is a no-brainer. The only optimization you do is getting out a group of 4 people.

think of why 4 is the unit of optimization. Say you can make 3 way call what would be the lowest no of call for N people for the same question.
: 1
« previous next »

 

Best RatedList All>>



Latest
Random



SMF 2.0.10 | SMF © 2015, Simple Machines | Contact Webmaster | OnlineFunDb.com © 2009/10 | Legal Disclaimer