The Celebrity Problem

Problem Statement

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 these 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 a 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

Implementation

C++ Program for The Celebrity Problem

#include <bits/stdc++.h>
using namespace std;
//Function to find the id of celebrity
int FindCelebId(int a,int n)
{
    int A = 0,B = n - 1; 
    //Finding celebity
    while(A < B)
    {
        if(a[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) && (a[A][i] || !a[i][A]))
       {
            return -1;
       }
    }
 
    return A;
}
   
//main function
int main()
{
   //Number of people
    int n;
    int a[n][n]; 
    for(int i=0;i<n;i++) 
    { 
        for(int j=0;j<n;j++) 
        { 
            cin>>a[i][j]; 
        } 
    }
    int x = FindCelebId(a,n);
    if(x == -1){
        cout<<"No Celebrity found"; 
    }
    else{
        cout<<"Celebrity id is: "<<x;
    }
    return 0;
}

import java.util.Scanner;
class sum
{
    public static int FindCelebId(int a[][], int n)
    {
        int A = 0,B = n - 1; 
        //Finding celebity
        while(A < B)
        {
            if(a[A][B]==1)
            {
                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) && (a[A][i]==1 || a[i][A]==0))
           {
                return -1;
           }
        }
        return A;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[][] = new int[n][n];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                a[i][j] = sr.nextInt();
            }
        }
        int x = FindCelebId(a,n);
        if(x == -1)
        {
            System.out.println("No Celebrity found"); 
        }
        else
        {
            System.out.println("Celebrity id is: " + x);
        }
    }
}

4
0 0 1 0
0 0 1 0
0 0 1 0
0 0 1 0

Celebrity id is: 2