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