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 <senthilnathan.maadas...@gmail.com> 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 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.