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.
