The Celebrity Problem

In a room of N people, Find the celebrity.

Conditions for Celebrity

If A is Celebrity then,

a) Everyone else in the room should know A
b) A shouldn’t know anyone in the room.

We need to find the person who satisfies this conditions.

Example

Algorithm

Time complexity : O(n)

a. We maintain two pointers at the start and end corners. (a, b)

b. In the given matrix value

    1. If Matrix[A][B] = 1, then A knows B

    2. Else, A doesn’t know B

c. Keep moving the pointers A and B such that, if A knows B move A. Else, move A. Do this Until

A < B.

d.  Finally check if A is celebrity or not by using two conditions:

    1. For all i, i should know A, except i not equal to A

    2. For all i, A shouldn’t know i

C++ Program

#include <bits/stdc++.h>

using namespace std;
#define N 8
 
//In this Matrix
//if i knows j then Matrix[i][j] = 1, Else 0 
bool  Matrix[N][N] = {{0, 0, 0, 1, 0},
                      {0, 0, 0, 1, 0},
                      {0, 0, 0, 1, 0},
                      {0, 0, 0, 0, 0},
                      {0, 0, 0, 1, 0}
};

bool Knows(int A, int B)
{
    return Matrix[A][B];
}
//Function to find the id of celebrity
int FindCelebId(int n)
{
    int A = 0,B = n - 1; 
    //Finding celebity
    while(A < B)
    {
        if(Knows(A,B))
        {
            A++;
        }
        else
        {
            B--;
        }
    }
    //Check celebrity conditions
    //If A is celebrity
    //All members should know A
    //A should not now anyone
    for (int i = 0; i < n; i++)
    {
       if ((i != A) && (Knows(A, i) || !Knows(i, A)))
       {
            return -1;
       }
    }
 
    return A;
}
   
//main function
int main()
{
   //Number of people
    int Num = 4;
    int x = FindCelebId(Num);
    if(x == -1){
        cout<<"No Celebrity found"; 
    }
    else{
        cout<<"Celebrity id is: "<<x;
    }
    return 0;
}
Try It


Next > < Prev
Scroll to Top