Optimal solution for the "celebrity" algorithm

Question

Among n persons,a "celebrity" is defined as someone who is known by everyone but does not know anyone. The problem is to identify the celebrity, if one exists, by asking the question only of the form, "Excuse me, do you know the person over there?" (The assumption is that all the answers are correct, and even that celebrity will also answer.) The goal is to minimize the number of questions.

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

Cimon

Does this helps geeksforgeeks.org/the-celebrity-problem – Cubical

I'm voting to close this question as off-topic because in its current form it is not a programming question. – Interceptor

Unless you are going for any assumption or any probabilistic derivatives, I think you have provided enough constraints for the solution to be n^2 – Pictor

yaa it does. thanks @Cubical – Cimon

check the birthday problem, i think it is related in that the optimum number of questions should be asked in the converse form by changing "same birthday as you" to "do you know this person" – War

celebrity problem analysis and algorithm and here – War

Answer 1

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.

War

Answer 2

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

Persia

@NikosM: yes, but as the number of items to be processed halves in every iteration, total cost is not O(NlogN) but just O(N). – Persia

Great solution! Yes, It's O(N) – Release

Answer 3

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

Ciborium

Answer 4

This question can be solved using graphs (indegree and outdegree concept) in O(N^2) Time complexity.

We can also solve this question in O(N) time and O(1) space using a simple two-pointer concept. We are going to compare two persons at a time one from beginning and other from the end and we will remove that person from consideration which cannot be a celebrity. For example, if there are two persons X and Y and X can identify person Y then surely X cannot be a celebrity as it knows a person inside this party. Another case would be when X does not know Y and in this case, Y cannot be a celebrity as there is at least one person who does not know him/her inside a party. Using this intuition two-pointer concept can be applied to find the celebrity inside this party.

I found a good explanatory video on Youtube by algods.

You can refer to this video for a better explanation.

Video Link:

https://youtu.be/aENYremq77I

Cremate

Answer 5

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;
}

Katti

Answer 6

This is how I did it :)

Question - A celebrity is defined someone whom everyone else knows of, but do not know anyone. Given N people (indexed 0...(N-1)), and a function knowsOf defined as follows: knowsOf(int person0, int person1) = true if person 0 knows person 1, and false otherwise Find out the celebrity in the N given people if there is any.

// return -1 if there is no celeb otherwise return person 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;
  }
 }

Costanzia

Answer 7

public class Solution {
    public int findCelebrity(int n) {
        if (n <= 1) {
            return -1;
        }

        int left = 0;
        int right = n - 1;

        // First find the right candidate known by everyone, but doesn't know anyone.
        while (left < right) {
            if (knows(left, right)) {
                left++;
            } else {
                right--;
            }
        }

        // Validate if the candidate knows none and everyone knows him.
        int candidate = right;
        for (int i = 0; i < n; i++) {
            if (i != candidate && (!knows(i, candidate) || knows(candidate, i))) {
                return -1;
            }
        }

        return candidate;
    }
}

Stench

Welcome to SO, please provide some explanation for your code to make it more understandable. – Backbreaker

Answer 8

int findCelebrity(int n) {
    int i=0;
    for(int j=1;j<n;j++){
        if(knows(i,j)){
            i=j;
        }
    }
        
    for(int j=0;j<n;j++){
        if(j!=i && (knows(i,j)|| !knows(j,i))){
             return -1;
        } 
    }
    return i;
}

Evangelistic

Where is knows coming from? What does it do? Also, a little bit of context on your code is beneficial to future readers of this thread. – Stroll

knows(int i, int j) is a boolean function which returns true if i knows j else false. This is known information from question. In first for loop, If knows(i,j) is true, 'i' is definitely not the celebrity, so, make i=j else continue. After the first for loop, 'i' equals to a person who could be a potential celebrity. In the second for loop, we are just making sure if 'i' is an actual celebrity or not. So, In total we are asking 2N-1 questions. – Evangelistic

Answer 9

Two Pointer

 int celebrity(vector<vector<int>>& mat) {
      int n = mat.size();
      
      int p1 = 0;
      int p2 = n - 1;
      
      while (p1 < p2) {
          if (mat[p1][p2] == 1) {
              p1++;
          } else {
              p2--;
          }
      }
      
      int celebrity = p1;
      for (int i = 0; i < n; i++) {
        if (i != celebrity) {
            if (mat[i][celebrity] == 0 || mat[celebrity][i] == 1) {
                return -1;
            }
        }
      }
      
      return celebrity;
  }

Mammillate

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Seka