# The Celebrity Problem

0
563

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

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