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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.