Geek Answers Handbook

Optimal solution for the celebrity algorithm

Among n individuals, “celebrity” is defined as someone who is known to everyone but does not know anyone . the problem is to identify the celebrity, if one exists, the question is only about the form: “Sorry, do you know the person there?” (It is assumed that all the answers are correct, and even this celebrity will also answer.) The goal is to minimize number of questions.

Is there a solution of order less than the obvious O(n^2) here?

+7
source share
5 answers

Using celebrity problem analysis here

Brute force decision. A graph has at most n(n-1) edges, and we can calculate it by asking a question for each potential edge. At this point, we can check whether the vertex is an absorber by calculating it independent of it. This brute force solution asks n(n-1) questions. Next, we show how to do this in no more than 3(n-1) questions and a linear location.

An elegant solution. Our algorithm consists of two stages: at the stage of exclusion, we exclude all but one person from the celebrity; at the verification stage, we check whether this remaining person is really a celebrity. The elimination phase keeps a list of possible celebrities. It originally contains all n people. At each iteration, we remove one person from the list. We use the following key observation: if person 1 knows person 2 , then person 1 not a celebrity; if person 1 does not know person 2 , then person 2 not a celebrity. Thus, asking person 1 if he knows person 2 , we can exclude any person 1 or person 2 from the list of possible celebrities. We can repeatedly use this idea to eliminate all people except one, say, person p . Now we check with brute force whether p celebrity: for every other person i we ask person p if he knows person i , and we ask people i if they know person p . If person p always answers no, and other people always answer yes, we declare person p as a celebrity. Otherwise, we are not in this group of celebrities.

+10
source

  • Divide all the people in pairs.

  • For each pair (A, B), specify A if he knows B.

    • If the answer is yes, A cannot be a celebrity, drop it.
    • If the answer is no, B cannot be a celebrity, drop it.

    Now only half the people are left.

  • Repeat from 1 until only one person remains.

Cost O (N).

+8
source

Here is the O (N) time algorithm

  • Push all the items onto the stack.
  • Remove the top two elements (e.g. A and B) and save A if B knows that A and A do not know B.
  • Delete both A, B both know each other or both do not know each other
+2
source

Here is my solution.

  #include<iostream> using namespace std; int main(){ int n; //number of celebrities cin>>n; int a[n][n]; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ cin>>a[i][j]; } } int count = 0; for(int i = 0;i < n;i++){ int pos = 0; for(int j = 0;j < n;j++){ if(a[i][j] == 0){ count = count + 1; } else{ count = 0; break; } } if(count == n){ pos = i; cout<<pos; break; } } return 0; }
0
source

Here is how I did it :)

Question. A celebrity is someone who everyone else knows about, but does not know anyone. Given N people (with index 0 ... (N -1)), and the function knows that it is defined as follows: knows that (int person0, int person1) = true if person 0 knows person 1, and false, in otherwise, find out the celebrity in N given to people, if any.

// return -1 if there is no celebrity, otherwise return the person’s index / number.

  public int celeb(int n) { int probaleCeleb = 0; for(int i =1 ; i < n; i++) { if(knowsOf(probaleCeleb , i)) { // true /false probaleCeleb = i; } } for(int i =0 ; i < n; i++) { if( i != probaleCeleb && (!knowsOf( i , probaleCeleb) || (knowsOf( probaleCeleb , i)) ) { probaleCeleb = -1; break; } } return probaleCeleb; } }
0
source

More articles:


All Articles