Problem
Given the group of people in party find the group of celebrities
Suppose we have N people and there might be a group of celebrities inside.
Every person knows every celebrity and every celebrity knows only every other celebrity.
If you are given the function of Knows(x,y) which returns true if x knows y, false otherwise. identify the group of celebrities.
This problem is to identify a group of celebrities, and it is not identifying the only celebrity among the people, such as http://k2code.blogspot.in/2014/04/the-celebrity-problem.html.
Solution
Method 1 - Brute force
Using brute force is easy. I can construct all possible sub-sequences of N people and filter them with the condition (everyone knows every celebrity and every celebrity knows only other celebrity)..
Also I know there must be only one celebrity group or none.
Method 2 - Linear solution
int find\_a\_celebrity()
{
int C = 0; // C is a potential celebrity
for( int i=0 ; i<N ; ++i )
if( !knows(i,C) ) // C is not a celebrity nor are all j<i, but i might be.
C = i;
for( int i=0 ; i<N ; ++i ) // Loop a second time to check everyone knows C.
if( !knows(i,C) ) return -1;
return C;
}
int C = find\_a\_celebrity();
If C==-1 then there are no celebrities. Otherwise the set { y | knows(C,y) } is the set of all celebrities. All together, this took at most 3 iterations through all N people, so this is discovered in time O(N).