# The Celebrity Problem  Difficulty Level Medium
Array Matrix Stack

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

Check given array of size n can represent BST of n levels or not

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

### Java Program for The Celebrity Problem

```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`

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