Problem

Every person knows every celebrity and every celebrity knows only every other celebrity.

If you are given the function of

This problem is to

Solution

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.

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).

http://stackoverflow.com/questions/20983260/linear-algorithm-for-finding-the-celebrity-group-not-single-celebrity

Given the group of people in party find the group of celebritiesSuppose 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).

**References**http://stackoverflow.com/questions/20983260/linear-algorithm-for-finding-the-celebrity-group-not-single-celebrity

## 0 comments:

## Post a Comment