@coolfrog
in case of AB we asked to A know B after checking this we eliminate A n same
case go for CD den
A B CD
| |
A D
AD Same approach
|
D (D will be celebrity)
On Fri, Sep 24, 2010 at 10:57 AM, kartheek muthyala
<[email protected]>wrote:
> @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$ <
> [email protected]> 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 <
>> [email protected]> 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 <
>>> [email protected]> 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 [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected]<algogeeks%[email protected]>
>>>> .
>>>> 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 [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected]<algogeeks%[email protected]>
>>> .
>>> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Thanks & Regards
Umesh kewat
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
