## Thursday, March 29, 2012

### Celebrities

In a group of persons, a celebrity is know by everyone and all the other people are known by none. Detect all the celebreties

1. Based on problem reduction.

Given N celebrities. Exclude N-1 celebrities which can be found recursively. If the N-th celebrity (?) knew the celebrity of N-1 celebrities, and the celebrity of N-1 group doesn't know N-th celebrity, our answer is (N-1)-th celebrity. Otherwise, better by pseudo code

int celebrity(Queue[1...N])
{
remove N;
c = celebrity(Queue[1...N-1])

if( N know c ) // possible that c can be
{
if( c doesn't know N ) return c;
else return -1; (No celebrity)
}
// directed graph, failing if doesn't imply that
// c know N
else if( c know N )
{
if( N doesn't know c ) return N;
else return -1; (No celebrity)
}

return -1; (No celebrity) // data incorrect
}

But the run time is O(n^2) :(. Any other better approach? May be like Moore's elimination voting algorithm?

2. http://www.geeksforgeeks.org/archives/19622