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?
Based on problem reduction.
ReplyDeleteGiven 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?
http://www.geeksforgeeks.org/archives/19622
ReplyDelete