Optimal solution for the "celebrity" algorithm

Using the analysis of the celebrity problem here

Brute-force solution. The graph has at most n(n-1) edges, and we can compute it by asking a question for each potential edge. At this point, we can check whether a vertex is a sink by computing its indegree and its outdegree. This brute-force solution asks n(n-1) questions. Next we show how to to do this with at most 3(n-1) questions and linear place.

An elegant solution. Our algorithm consists of two phases: in the elimination phase, we eliminate all but one person from being the celebrity; in the verification phase we check whether this one remaining person is indeed a celebrity. The elimination phase maintains a list of possible celebrities. Initially it contains all n people. In each iteration, we delete one person from the list. We exploit the following key observation: if person 1 knows person 2, then person 1 is not a celebrity; if person 1 does not know person 2, then person 2 is not a celebrity. Thus, by asking person 1 if he knows person 2, we can eliminate either person 1 or person 2 from the list of possible celebrities. We can use this idea repeatedly to eliminate all people but one, say person p. We now verify by brute force whether p is a celebrity: for every other person i , we ask person p whether he knows person i , and we ask persons i whether they know person p . If person p always answers no, and the other people always answer yes, the we declare person p as the celebrity. Otherwise, we conclude there is no celebrity in this group.

1. Divide all the people in pairs.

2. For every pair (A, B), ask A if he knows B.

   • if the answer is yes, A can not be the celebrity, discard him.
   • if the answer is no, B can not be the celebrity, discard him.

   Now, only half the people remains.

3. Repeat from 1 until just one person remains.

Cost O(N).

Here is O(N) time algorithm

1. Push all the elements into stack.
2. Remove top two elements(say A and B), and keep A if B knows A and A does not know B.
3. Remove both A,B is both know each other or both does not know each other