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

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