Home » Technical Interview Questions » Array Interview Questions » The Celebrity Problem

The Celebrity Problem


Reading Time - 4 mins

In the celebrity problem there is a room of N people, Find the celebrity. Conditions for Celebrity is-

If A is Celebrity then

  • Everyone else in the room should know A.
  • A shouldn’t know anyone in the room.

We need to find the person who satisfies this conditions.

Example

Input

knows[] = {

{0, 0, 1, 0},

{ 0, 0, 1, 0},

{0, 0, 0, 0},

{0, 0, 1, 0} }

Output

Celebrity id is: 2

Explanation

The person with ID 2 does not know anyone but everyone knows him.

Algorithm for The Celebrity Problem

Now we know the problem statement, So we quickly move to the algorithm used for the problem. Here we first fix the column in the matrix first. For fixing the column we moving the pointers A and B in such a way that if A knows B then increase A else increase B. Do this Until A < B. Now once we set the column then, Check celebrity if A is celebrity then all members should know A and A should not now anyone. Now if we got celebrity condition fine then print the id of person else print -1.

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

2. In the given matrix value

  • If Matrix[A][B] = 1, then A knows B
  • Else, A doesn’t know B
  • Keep moving the pointers A and B such that, if A knows B move A. Else, move B. Do this Until A < B.

3.  Finally, check if A is a celebrity or not by using two conditions:

  •  For all i, i should know A, except i not equal to A
  •  For all i, A shouldn’t know i
READ  Double the first element and move zero to end

C++ Program for The Celebrity Problem

#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;
}
Celebrity id is: 3

Complexity Analysis

Time complexity

O(n) where n is the number of elements present in the room. Here we iterate the particular raw which leads us to linear time complexity.

Space Complexity

O(1) because we don’t create any extra space while calculating the result.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions