let S be the set containing n people
int i=0,j=n-1;
while(i!=j)
{
*ask S[i] if he knows S[j]*/
if(YES)
i++; //if yes then S[i] cant be the celebrity take him
out of the equation
else
j--; //if no then S[j] cant be the celebrity so let him
pass
}
S[i] or S[j] gives the celebrity in the set;
Complexity:
(max no of times i can be incremented)+(max no of times j can be
decremented)=n
no of questions=n
so O(n)
Bhupendra Dubey
DELHI COLLEGE OF ENGINEERING
On Tue, Dec 21, 2010 at 9:26 AM, sharat <sharath.channaha...@gmail.com>wrote:
> 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<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
bhupendra dubey
--
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.
