@coolfrog,
What I meant by remained is
Considering your case of A,B,C,D and B is the celebrity,
The sequence is
First A,B ask the question to A, then remained=B
Then B,C ask the question to B, then remained=B
Then B,D ask the question to B, then remained= B
Then ask A,C,D whether they know B
Then ask B whether they know A,C,D
So, that's how I said 3(n-1) questions...
Correct me if I am wrong
On Thu, Sep 23, 2010 at 8:32 PM, coolfrog$
<dixit.coolfrog.div...@gmail.com>wrote:
>
> @kartheek
> i am getting. this prudent approach....
> but what is "add what remained to the remainder."
> suppose u have A,B,C,D and B is celebrity ...
>
> if( A knows B)
> { A is not celb.
> if( B knows C){}
> else{ C is not celb.
> if (C knows B )
> { if( D knows B)
> { D is not celb.
> only B remain... hence it celeb...
> /* suppose if u have A,B,C,D,E
> and B is celeb.
> then again if (E knows B)
> { E is not
> celb....
> only B
> remain... hence it celeb...
> }
> */
> }
> }
> }
> }
> look in every if condition we are Asking Sequentially to A
> ,B,C,D,E.......
> can these be correct solution ....
> correct me plz... if wrong......
> On Thu, Sep 23, 2010 at 12:56 AM, kartheek muthyala <
> kartheek0...@gmail.com> wrote:
>
>> Take 2 persons, suppose say A and B
>> ask one of them the question about other
>> if A Knows B, then A cannot be the celebrity,
>> if A does not know B, then B cannot be the celebrity.
>> add what remained to the remainder.
>>
>> repeat this process for the remaining n-1 until one or none remained.
>>
>> Then if it is none then there is no celebrity.
>> If there is one ask the question whether this person is known by remaining
>> n-1 and this person does n't know the remaining n-1. So a total of 3(n-1)
>> questions is used to determine the celeb.
>>
>> Time complexity is O(n).
>>
>> Repeat this for the remaining n-1 persons, if the remainder contain one
>> then
>>
>>
>> On Wed, Sep 22, 2010 at 9:37 PM, Divesh Dixit <
>> dixit.coolfrog.div...@gmail.com> wrote:
>>
>>> Among n people, a celebrity is defined as someone who is known to
>>> everyone, but who knows no
>>> one. Design and analyze to identify the celebrity, if one exists, by
>>> asking only questions of the
>>> following form: "Excuse me, do you know person x?" You will get a
>>> binary answer for each such
>>> question asked. Find the celebrity by asking only O(n) questions.
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
