@ umesh kewat
suppose A,B,C,D and D is celebrity
A,B C,D
how would u eliminate one form A,B even if u can ... it will be order
of O(n logn) ...
Regards ...
Divesh
On Thu, Sep 23, 2010 at 4:00 AM, umesh kewat <[email protected]> wrote:
> Use divide and conquer strategy of algorithm by diving in 2-2 group like
> merge sort make tree where every level we dropping people by using logic of
> above post so root will be celebrity
>
>
> On Thu, Sep 23, 2010 at 11:26 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.
>>
>
>
>
> --
> 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]<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.
