@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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
