It can be thought of as a binary tree
Assume n=8.
At first level all 8 people are present, i.e leaves of the tree. 1
asks 2 if 2 knows 1, 3 asks 4 if 4 knows 3 etc ..
If 2 knows 1, then 1 goes to next level, else 2. Thus n/2 questions
are asked at level 1 and the height will be log(n). The total
questions asked will n.
1 2 3 4 5 6 7 8
1 4 5 8
1 5 8
5 8
8
On Dec 19, 4:25 pm, Senthilnathan Maadasamy
<[email protected]> wrote:
> Note that there cannot be more than one celebrity in the group.
>
> Here is an O(n) solution:
>
> Choose a random candidate x as a possible celebrity.
> Let S be the set of remaining n-1 candidates.
>
> While (S is not empty)
> Remove another candidate y from S and ask if y follows x.
> If y follows x, y is not a celebrity.
> If y does not follow x, x is not a celebrity and hence let
> y be the new x.
>
> After this, we are left with only one possible celebrity x. We still
> need to verify if x is actually a celebrity.
> Check if the remaining n-1 candidates follow x.
> If yes, x is a celebrity.
> If no, there is no celebrity in the group.
--
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.
