The function returns the id Celebrity Celebrity
Celebrities int (S group of people) {
If | S | = 1 then {
Let x in S
return x
else{
Choose x, y in S
If x follows y then {S = S - {s} x = x}
Else if x follows y then{ S = S - {y}, s = y;}
Else ERROR ("no celebrity")
k = Celebrities(S)
If s follow k and k does not follow s then
return k
}
}
Worst Case O (4 (n-1)): (
Best Case O(1)
The function returns the id Celebrity Celebrity
Celebrities int (S group of people) {
If | S | = 1 then {
Let x in S
return x
else{
Choose x, y in S
If x follows y then {S = S - {s} x = x}
Else{ S = S - {y}, s = y;}
k = Celebrities(S)
If s follow k and k does not follow s then
return k
}
}
Worst Case O(3(n-1))
Best Case O(3(n-1))
Wladimir Araujo Tavares
*Federal University of Ceará
*
On Tue, Dec 21, 2010 at 9:25 AM, bhupendra dubey <[email protected]>wrote:
> 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 <[email protected]>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
>> <[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.
>>
>>
>
>
> --
> 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 [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.
>
--
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.
