Open In App

The Celebrity Problem

Last Updated : 24 May, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

In a party of N people, only one person is known to everyone. Such a person may be present at the party, if yes, (s)he doesn’t know anyone at the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in the minimum number of questions.
We can describe the problem input as an array of numbers/characters representing persons in the party. We also have a hypothetical function HaveAcquaintance(A, B) which returns true if A knows B, and false otherwise. How can we solve the problem? 

Examples:  

Input:
MATRIX = { {0, 0, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 1, 0} }
Output: id = 2
Explanation: The person with ID 2 does not know anyone but everyone knows him

Input:
MATRIX = { {0, 0, 1, 0}, {0, 0, 1, 0}, {0, 1, 0, 0}, {0, 0, 1, 0} }
Output: No celebrity
Explanation: There is no celebrity.

Recommended Practice

Basic and Approach Using Adjacency list.

 Approach : 

As we are given A square NxN matrix M[][] is used to represent people at the party such that if an element of row i and column j is set to 1 ( M[i][j] = 1) it means ith person knows jth person. So it is an Directed Graph we create adjacency list and check for if any adjacency list empty means the person do not know any one in party then we check if all other person in party know him then the person(i) is celebrity return index i if not then find continue.

Follow the steps below to solve the problem :

  • traverse over given matrix and make adjacency list.
  • make a directed edge from i to j if m[i][j]==1 in adjacency list.
  • now we need to traverse over 0 to n.
  • and check weather adj[i].empty() if true then check that i is present in all other adjacency list from 0 to n.
  • if all other person know i then he is celebrity simply return i.
  • if know one satisfy above condition retrun -1.

Below is the implementation of the above approach :

C++
#include <iostream>
#include<bits/stdc++.h>
using namespace std;

 int celebrity(vector<vector<int>>&M, int n){
        // code here 
        vector<int>adj[n+1];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(M[i][j]==1){
                    adj[i].push_back(j);
                }
            }
        }
        vector<int>::iterator it;
        for(int i=0;i<n;i++){
            if(adj[i].empty()){
                bool flag=1;
                for(int j=0;j<n;j++){
                    if(i==j)continue;
                    it=find(adj[j].begin(),adj[j].end(),i);
                    if(it==adj[j].end()){
                        flag=0;
                        break;
                    }
                }
                if(flag)return i;
            }
        }
        return -1;
    }

int main() {
    vector<vector<int>>M{ {0, 0, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 1, 0} };
    int n=M.size();
    int Celebrity=celebrity(M,n);
    if(Celebrity!=-1){
      cout<<"Celebrity is : "<<Celebrity<<endl;
    }else{
      cout<<"No celebrity"<<endl;
    }
  //Code and Approach Contributed By Sanket Gode.
    return 0;
}
Java
import java.util.*;

public class Main {
public static int celebrity(ArrayList<ArrayList<Integer>> M, int n) {
ArrayList<Integer>[] adj = new ArrayList[n];
for (int i = 0; i < n; i++) {
adj[i] = new ArrayList<Integer>();
for (int j = 0; j < n; j++) {
if (M.get(i).get(j) == 1) {
adj[i].add(j);
}
}
}
for (int i = 0; i < n; i++) {
if (adj[i].isEmpty()) {
boolean flag = true;
for (int j = 0; j < n; j++) {
if (i == j)
continue;
if (!adj[j].contains(i)) {
flag = false;
break;
}
}
if (flag)
return i;
}
}
return -1;
}
  public static void main(String[] args) {
    ArrayList<ArrayList<Integer>> M = new ArrayList<>();
    M.add(new ArrayList<Integer>(Arrays.asList(0, 0, 1, 0)));
    M.add(new ArrayList<Integer>(Arrays.asList(0, 0, 1, 0)));
    M.add(new ArrayList<Integer>(Arrays.asList(0, 0, 0, 0)));
    M.add(new ArrayList<Integer>(Arrays.asList(0, 0, 1, 0)));

    int n = M.size();
    int Celebrity = celebrity(M, n);

    if (Celebrity != -1) {
        System.out.println("Celebrity is : " + Celebrity);
    } else {
        System.out.println("No celebrity");
    }
}
}
Python
def celebrity(M, n):
  
    # Create an adjacency list for each person
    adj = [[] for i in range(n)]
    for i in range(n):
        for j in range(n):
            if M[i][j] == 1:
                adj[i].append(j)
                
    # Check if there is a person 
    # who doesn't know anyone but 
    # everyone knows him/her
    for i in range(n):
        if not adj[i]:
            flag = True
            for j in range(n):
                if i == j:
                    continue
                if i not in adj[j]:
                    flag = False
                    break
            if flag:
                return i
    return -1

# Sample input
M = [[0, 0, 1, 0], [0, 0, 1, 0], [0, 0, 0, 0], [0, 0, 1, 0]]
n = len(M)
Celebrity = celebrity(M, n)
if Celebrity != -1:
    print("Celebrity is : ", Celebrity)
else:
    print("No celebrity")
C#
using System;
using System.Collections.Generic;

public class MainClass {
    public static int Celebrity(List<List<int> > M, int n)
    {
        List<int>[] adj = new List<int>[ n ];
        for (int i = 0; i < n; i++) {
            adj[i] = new List<int>();
            for (int j = 0; j < n; j++) {
                if (M[i][j] == 1) {
                    adj[i].Add(j);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (adj[i].Count == 0) {
                bool flag = true;
                for (int j = 0; j < n; j++) {
                    if (i == j)
                        continue;
                    if (!adj[j].Contains(i)) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    return i;
            }
        }
        return -1;
    }

    public static void Main(string[] args)
    {
        List<List<int> > M = new List<List<int> >{
            new List<int>{ 0, 0, 1, 0 },
            new List<int>{ 0, 0, 1, 0 },
            new List<int>{ 0, 0, 0, 0 },
            new List<int>{ 0, 0, 1, 0 }
        };
        int n = M.Count;
        int CelebrityResult = Celebrity(M, n);

        if (CelebrityResult != -1) {
            Console.WriteLine("Celebrity is : "
                              + CelebrityResult);
        }
        else {
            Console.WriteLine("No celebrity");
        }
    }
}
Javascript
// Javascript code addition 

function celebrity(M) {
  const n = M.length;
  // Create an adjacency list for each person
  const adj = [];
  for (let i = 0; i < n; i++) {
    adj[i] = [];
    for (let j = 0; j < n; j++) {
      if (M[i][j] === 1) {
        adj[i].push(j);
      }
    }
  }
    
    // Check if there is a person 
    // who doesn't know anyone but 
    // everyone knows him/her
  for (let i = 0; i < n; i++) {
    if (adj[i].length === 0) {
      let flag = true;
      for (let j = 0; j < n; j++) {
        if (i === j) continue;
        if (!adj[j].includes(i)) {
          flag = false;
          break;
        }
      }
      if (flag) return i;
    }
  }
  return -1;
}

// Sample input
const M = [
  [0, 0, 1, 0],
  [0, 0, 1, 0],
  [0, 0, 0, 0],
  [0, 0, 1, 0]
];
const Celebrity = celebrity(M);
if (Celebrity !== -1) {
  console.log("Celebrity is: " + Celebrity);
} else {
  console.log("No celebrity");
}

// The code is contributed by Arushi Goel. 

Output
Celebrity is : 2

Complexity Analysis :

Time Complexity: O(N^2)
Auxiliary Space: O(N)

The Celebrity Problem uses Graph to arrive at a particular solution

Model the solution using graphs. Initialize indegree and outdegree of every vertex as 0. If A knows B, draw a directed edge from A to B, increase indegree of B and outdegree of A by 1. Construct all possible edges of the graph for every possible pair [i, j]. There are NC2 pairs. If a celebrity is present in the party, there will be one sink node in the graph with outdegree of zero and indegree of N-1. 

Follow the steps below to solve the problem:

  • Create two arrays indegree and outdegree, to store the indegree and outdegree
  • Run a nested loop, the outer loop from 0 to n and inner loop from 0 to n.
  • For every pair i, j check if i knows j then increase the outdegree of i and indegree of j.
  • For every pair i, j check if j knows i then increase the outdegree of j and indegree of i.
  • Run a loop from 0 to n and find the id where the indegree is n-1 and outdegree is 0.

Below is the implementation of the above approach:

C++
// C++ program to find celebrity
#include <bits/stdc++.h>
#include <list>
using namespace std;

// Max # of persons in the party
#define N 8

// Person with 2 is celebrity
bool MATRIX[N][N] = { { 0, 0, 1, 0 },
                      { 0, 0, 1, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 1, 0 } };

bool knows(int a, int b) { return MATRIX[a][b]; }

// Returns -1 if celebrity
// is not present. If present,
// returns id (value from 0 to n-1).
int findCelebrity(int n)
{
    // the graph needs not be constructed
    // as the edges can be found by
    // using knows function

    // degree array;
    int indegree[n] = { 0 }, outdegree[n] = { 0 };

    // query for all edges
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x = knows(i, j);

            // set the degrees
            outdegree[i] += x;
            indegree[j] += x;
        }
    }

    // find a person with indegree n-1
    // and out degree 0
    for (int i = 0; i < n; i++)
        if (indegree[i] == n - 1 && outdegree[i] == 0)
            return i;

    return -1;
}

// Driver code
int main()
{
    int n = 4;
    int id = findCelebrity(n);
    id == -1 ? cout << "No celebrity"
             : cout << "Celebrity ID " << id;
    return 0;
}
Java
// Java program to find celebrity
import java.util.*;
class GFG {

    // Max # of persons in the party
    static final int N = 8;

    // Person with 2 is celebrity
    static int MATRIX[][] = { { 0, 0, 1, 0 },
                              { 0, 0, 1, 0 },
                              { 0, 0, 0, 0 },
                              { 0, 0, 1, 0 } };

    static int knows(int a, int b) { return MATRIX[a][b]; }

    // Returns -1 if celebrity
    // is not present. If present,
    // returns id (value from 0 to n-1).
    static int findCelebrity(int n)
    {

        // the graph needs not be constructed
        // as the edges can be found by
        // using knows function

        // degree array;
        int[] indegree = new int[n];
        int[] outdegree = new int[n];

        // query for all edges
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int x = knows(i, j);

                // set the degrees
                outdegree[i] += x;
                indegree[j] += x;
            }
        }

        // find a person with indegree n-1
        // and out degree 0
        for (int i = 0; i < n; i++)
            if (indegree[i] == n - 1 && outdegree[i] == 0)
                return i;

        return -1;
    }

    // Driver code
    public static void main(String[] args)
    {
        int n = 4;
        int id = findCelebrity(n);
        if (id == -1)
            System.out.print("No celebrity");
        else
            System.out.print("Celebrity ID " + id);
    }
}

// This code is contributed by Rajput-Ji
Python
# Python3 program to find celebrity

# Max # of persons in the party
N = 8

# Person with 2 is celebrity
MATRIX = [[0, 0, 1, 0],
          [0, 0, 1, 0],
          [0, 0, 0, 0],
          [0, 0, 1, 0]]


def knows(a, b):

    return MATRIX[a][b]


def findCelebrity(n):

    # The graph needs not be constructed
    # as the edges can be found by
    # using knows function

    # degree array;
    indegree = [0 for x in range(n)]
    outdegree = [0 for x in range(n)]

    # Query for all edges
    for i in range(n):
        for j in range(n):
            x = knows(i, j)

            # Set the degrees
            outdegree[i] += x
            indegree[j] += x

    # Find a person with indegree n-1
    # and out degree 0
    for i in range(n):
        if (indegree[i] == n - 1 and
                outdegree[i] == 0):
            return i

    return -1


# Driver code
if __name__ == '__main__':

    n = 4
    id_ = findCelebrity(n)

    if id_ == -1:
        print("No celebrity")
    else:
        print("Celebrity ID", id_)

# This code is contributed by UnworthyProgrammer
C#
// C# program to find celebrity

using System;
public class GFG {

    // Max # of persons in the party
    static readonly int N = 8;

    // Person with 2 is celebrity
    static int[, ] MATRIX = { { 0, 0, 1, 0 },
                              { 0, 0, 1, 0 },
                              { 0, 0, 0, 0 },
                              { 0, 0, 1, 0 } };

    static int knows(int a, int b) { return MATRIX[a, b]; }

    // Returns -1 if celebrity
    // is not present. If present,
    // returns id (value from 0 to n-1).
    static int findCelebrity(int n)
    {

        // the graph needs not be constructed
        // as the edges can be found by
        // using knows function

        // degree array;
        int[] indegree = new int[n];
        int[] outdegree = new int[n];

        // query for all edges
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int x = knows(i, j);

                // set the degrees
                outdegree[i] += x;
                indegree[j] += x;
            }
        }

        // find a person with indegree n-1
        // and out degree 0
        for (int i = 0; i < n; i++)
            if (indegree[i] == n - 1 && outdegree[i] == 0)
                return i;

        return -1;
    }

    // Driver code
    public static void Main(String[] args)
    {
        int n = 4;
        int id = findCelebrity(n);
        if (id == -1)
            Console.Write("No celebrity");
        else
            Console.Write("Celebrity ID " + id);
    }
}

// This code is contributed by aashish1995
Javascript
// JavaScript program to find celebrity

    // Max # of persons in the party
      var N = 8;

    // Person with 2 is celebrity
    var MATRIX = [ [ 0, 0, 1, 0 ], 
                   [ 0, 0, 1, 0 ], 
                   [ 0, 0, 0, 0 ], 
                   [ 0, 0, 1, 0 ] ];

    function knows(a , b) {
        return MATRIX[a][b];
    }

    // Returns -1 if celebrity
    // is not present. If present,
    // returns id (value from 0 to n-1).
    function findCelebrity(n) {

        // the graph needs not be constructed
        // as the edges can be found by
        // using knows function

        // degree array;
        var indegree = Array(n).fill(0);
        var outdegree = Array(n).fill(0);

        // query for all edges
        for (var i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                var x = knows(i, j);

                // set the degrees
                outdegree[i] += x;
                indegree[j] += x;
            }
        }

        // find a person with indegree n-1
        // and out degree 0
        for (i = 0; i < n; i++)
            if (indegree[i] == n - 1 && outdegree[i] == 0)
                return i;

        return -1;
    }

    // Driver code
    
        var n = 4;
        var id = findCelebrity(n);
        if (id == -1)
            console.log("No celebrity");
        else
            console.log("Celebrity ID " + id);

// This code is contributed by todaysgaurav 

Output
Celebrity ID 2

Time Complexity: O(N2), A nested loop is run traversing the array
Auxiliary Space: O(N), Since extra space of size N is required.

The Celebrity Problem using Recursion:

The problem can be solved using recursion. Say, if the ‘potential celebrity’ of N-1 persons is known, can the solution to N be found from it? A potential celebrity is one who is the only one left after eliminating n-1 people. n-1 people are eliminated with the following strategy: 

  • If A knows B, then A cannot be a celebrity. But B could be.
  • Else If B knows A, then B cannot be a celebrity. But A could be.

The above-mentioned approach uses Recursion to find the potential celebrity among n persons, that recursively calls n-1 persons, till the base case of 0 persons is reached. For 0 persons -1 is returned indicating that there are no possible celebrities since there are 0 people. In the ith stage of recursion, the ith person and (i-1)th person are compared to check if anyone of them knows the other. And using the above logic (in the bullet points) the potential celebrity is returned to the (i+1)th stage.

Once the recursive function returns an id. We check if this id does not know anybody else, but all others know this id. If this is true, then this id will be the celebrity.

Follow the steps below to solve the problem:

  • Create a recursive function that takes an integer n.
  • Check the base case, if the value of n is 0 then return -1.
  • Call the recursive function and get the ID of the potential celebrity from the first n-1 elements.
  • If the id is -1 then assign n as the potential celebrity and return the value.
  • If the potential  celebrity of first n-1 elements knows n-1 then return n-1, (0 based indexing)
  • If the celebrity of the first n-1 elements does not know n-1 then return id of the celebrity of n-1 elements, (0 based indexing)
  • Else return -1.
  • Create a wrapper function and check whether the id returned by the function is really the celebrity or not.

Below is the implementation of the above approach:

C++
// C++ program to find celebrity
#include <bits/stdc++.h>
#include <list>
using namespace std;

// Max # of persons in the party
#define N 8

// Person with 2 is celebrity
bool MATRIX[N][N] = { { 0, 0, 1, 0 },
                      { 0, 0, 1, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 1, 0 } };

bool knows(int a, int b) { return MATRIX[a][b]; }

// Returns -1 if a 'potential celebrity'
// is not present. If present,
// returns id (value from 0 to n-1).
int findPotentialCelebrity(int n)
{
    // base case - when n reaches 0 , returns -1
    // since n represents the number of people,
    // 0 people implies no celebrity(= -1)
    if (n == 0)
        return -1;

    // find the celebrity with n-1
    // persons
    int id = findPotentialCelebrity(n - 1);

    // if there are no celebrities
    if (id == -1)
        return n - 1;

    // if the id knows the nth person
    // then the id cannot be a celebrity, but nth person
    // could be one
    else if (knows(id, n - 1)) {
        return n - 1;
    }
    // if the nth person knows the id,
    // then the nth person cannot be a celebrity and the id
    // could be one
    else if (knows(n - 1, id)) {
        return id;
    }

    // if there is no celebrity
    return -1;
}

// Returns -1 if celebrity
// is not present. If present,
// returns id (value from 0 to n-1).
// a wrapper over findCelebrity
int Celebrity(int n)
{
    // find the celebrity
    int id = findPotentialCelebrity(n);

    // check if the celebrity found
    // is really the celebrity
    if (id == -1)
        return id;
    else {
        int c1 = 0, c2 = 0;

        // check the id is really the
        // celebrity
        for (int i = 0; i < n; i++)
            if (i != id) {
                c1 += knows(id, i);
                c2 += knows(i, id);
            }

        // if the person is known to
        // everyone.
        if (c1 == 0 && c2 == n - 1)
            return id;

        return -1;
    }
}

// Driver code
int main()
{
    int n = 4;
    int id = Celebrity(n);
    id == -1 ? cout << "No celebrity"
             : cout << "Celebrity ID " << id;
    return 0;
}
Java
// Java program for the above approach
import java.io.*;

class GFG {

    // Max # of persons in the party
    static int N = 8;

    // Person with 2 is celebrity
    static int MATRIX[][] = { { 0, 0, 1, 0 },
                              { 0, 0, 1, 0 },
                              { 0, 0, 0, 0 },
                              { 0, 0, 1, 0 } };

    static int knows(int a, int b) { return MATRIX[a][b]; }

    // Returns -1 if a 'potential celebrity'
    // is not present. If present,
    // returns id (value from 0 to n-1).
    static int findPotentialCelebrity(int n)
    {
        // base case - when n reaches 0 , returns -1
        // since n represents the number of people,
        // 0 people implies no celebrity(= -1)
        if (n == 0)
            return -1;

        // find the celebrity with n-1
        // persons
        int id = findPotentialCelebrity(n - 1);

        // if there are no celebrities
        if (id == -1)
            return n - 1;

        // if the id knows the nth person
        // then the id cannot be a celebrity, but nth person
        // could be one
        else if (knows(id, n - 1) == 1) {
            return n - 1;
        }
        // if the nth person knows the id,
        // then the nth person cannot be a celebrity and the
        // id could be one
        else if (knows(n - 1, id) == 1) {
            return id;
        }

        // if there is no celebrity
        return -1;
    }

    // Returns -1 if celebrity
    // is not present. If present,
    // returns id (value from 0 to n-1).
    // a wrapper over findCelebrity
    static int Celebrity(int n)
    {
        // find the celebrity
        int id = findPotentialCelebrity(n);

        // check if the celebrity found
        // is really the celebrity
        if (id == -1)
            return id;
        else {
            int c1 = 0, c2 = 0;

            // check the id is really the
            // celebrity
            for (int i = 0; i < n; i++)
                if (i != id) {
                    c1 += knows(id, i);
                    c2 += knows(i, id);
                }

            // if the person is known to
            // everyone.
            if (c1 == 0 && c2 == n - 1)
                return id;

            return -1;
        }
    }

    // Driver code
    public static void main(String[] args)
    {
        int n = 4;
        int id = Celebrity(n);
        if (id == -1) {
            System.out.println("No celebrity");
        }
        else {
            System.out.println("Celebrity ID " + id);
        }
    }
}

// This code is contributed by Potta Lokesh
Python
# Python3 program to find celebrity

# Max # of persons in the party
N = 8

# Person with 2 is celebrity
MATRIX = [[0, 0, 1, 0],
          [0, 0, 1, 0],
          [0, 0, 0, 0],
          [0, 0, 1, 0]]


def knows(a, b):

    return MATRIX[a][b]

# Returns -1 if a potential celebrity
# is not present. If present,
# returns id (value from 0 to n-1).


def findPotentialCelebrity(n):

    # Base case
    if (n == 0):
        return 0

    # Find the celebrity with n-1
    # persons
    id_ = findPotentialCelebrity(n - 1)

    # If there are no celebrities
    if (id_ == -1):
        return n - 1
    # if the id knows the nth person
    # then the id cannot be a celebrity, but nth person
    # could be on
    elif knows(id_, n - 1):
        return n - 1
    # if the id knows the nth person
    # then the id cannot be a celebrity, but nth person
    # could be one
    elif knows(n - 1, id_):
        return id_
    # If there is no celebrity
    return - 1

# Returns -1 if celebrity
# is not present. If present,
# returns id (value from 0 to n-1).
# a wrapper over findCelebrity


def Celebrity(n):

    # Find the celebrity
    id_ = findPotentialCelebrity(n)

    # Check if the celebrity found
    # is really the celebrity
    if (id_ == -1):
        return id_
    else:
        c1 = 0
        c2 = 0

        # Check the id is really the
        # celebrity
        for i in range(n):
            if (i != id_):
                c1 += knows(id_, i)
                c2 += knows(i, id_)

        # If the person is known to
        # everyone.
        if (c1 == 0 and c2 == n - 1):
            return id_

        return -1


# Driver code
if __name__ == '__main__':

    n = 4
    id_ = Celebrity(n)

    if id_ == -1:
        print("No celebrity")
    else:
        print("Celebrity ID", id_)

# This code is contributed by UnworthyProgrammer
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {

    // Max # of persons in the party
    static int N = 8;

    // Person with 2 is celebrity
    static int[, ] MATRIX = { { 0, 0, 1, 0 },
                              { 0, 0, 1, 0 },
                              { 0, 0, 0, 0 },
                              { 0, 0, 1, 0 } };

    static int knows(int a, int b) { return MATRIX[a, b]; }

    // Returns -1 if a 'potential celebrity'
    // is not present. If present,
    // returns id (value from 0 to n-1).
    static int findPotentialCelebrity(int n)
    {

        // base case - when n reaches 0 , returns -1
        // since n represents the number of people,
        // 0 people implies no celebrity(= -1)
        if (n == 0)
            return -1;

        // find the celebrity with n-1
        // persons
        int id = findPotentialCelebrity(n - 1);

        // if there are no celebrities
        if (id == -1)
            return n - 1;

        // if the id knows the nth person
        // then the id cannot be a celebrity, but nth person
        // could be one
        else if (knows(id, n - 1) == 1) {
            return n - 1;
        }

        // if the nth person knows the id,
        // then the nth person cannot be a celebrity and the
        // id could be one
        else if (knows(n - 1, id) == 1) {
            return id;
        }

        // if there is no celebrity
        return -1;
    }

    // Returns -1 if celebrity
    // is not present. If present,
    // returns id (value from 0 to n-1).
    // a wrapper over findCelebrity
    static int Celebrity(int n)
    {

        // find the celebrity
        int id = findPotentialCelebrity(n);

        // check if the celebrity found
        // is really the celebrity
        if (id == -1)
            return id;
        else {
            int c1 = 0, c2 = 0;

            // check the id is really the
            // celebrity
            for (int i = 0; i < n; i++)
                if (i != id) {
                    c1 += knows(id, i);
                    c2 += knows(i, id);
                }

            // if the person is known to
            // everyone.
            if (c1 == 0 && c2 == n - 1)
                return id;

            return -1;
        }
    }

    // Driver code
    public static void Main(String[] args)
    {
        int n = 4;
        int id = Celebrity(n);
        if (id == -1) {
            Console.WriteLine("No celebrity");
        }
        else {
            Console.WriteLine("Celebrity ID " + id);
        }
    }
}

// This code is contributed by gauravrajput1
Javascript
// JavaScript program for the above approach
// Max # of persons in the party
var N = 8;

    // Person with 2 is celebrity
    var MATRIX = [ [ 0, 0, 1, 0 ],
                              [ 0, 0, 1, 0 ],
                              [ 0, 0, 0, 0 ],
                              [ 0, 0, 1, 0 ] ];

    function knows(a, b) 
    {
        return MATRIX[a][b]; 
        
    }

    // Returns -1 if a 'potential celebrity'
    // is not present. If present,
    // returns id (value from 0 to n-1).
    function findPotentialCelebrity(n)
    {
        // base case - when n reaches 0 , returns -1
        // since n represents the number of people,
        // 0 people implies no celebrity(= -1)
        if (n == 0)
            return -1;

        // find the celebrity with n-1
        // persons
        var id = findPotentialCelebrity(n - 1);

        // if there are no celebrities
        if (id == -1)
            return n - 1;

        // if the id knows the nth person
        // then the id cannot be a celebrity, but nth person
        // could be one
        else if (knows(id, n - 1) == 1) {
            return n - 1;
        }
        // if the nth person knows the id,
        // then the nth person cannot be a celebrity and the
        // id could be one
        else if (knows(n - 1, id) == 1) {
            return id;
        }

        // if there is no celebrity
        return -1;
    }

    // Returns -1 if celebrity
    // is not present. If present,
    // returns id (value from 0 to n-1).
    // a wrapper over findCelebrity
    function Celebrity(n)
    {
        // find the celebrity
        var id = findPotentialCelebrity(n);

        // check if the celebrity found
        // is really the celebrity
        if (id == -1)
            return id;
        else {
            var c1 = 0, c2 = 0;

            // check the id is really the
            // celebrity
            for (var i = 0; i < n; i++)
                if (i != id) {
                    c1 += knows(id, i);
                    c2 += knows(i, id);
                }

            // if the person is known to
            // everyone.
            if (c1 == 0 && c2 == n - 1)
                return id;

            return -1;
        }
    }

    // Driver code
        var n = 4;
        var id = Celebrity(n);
        if (id == -1) {
            console.log("No celebrity");
        }
        else {
            console.log("Celebrity ID " + id);
        }
    
// This code is contributed by shivanisinghss2110

Output
Celebrity ID 2

Time Complexity: O(N), The recursive function is called n times.
Auxiliary Space: O(N), Recursive call of N times use stack of size N.

The Celebrity Problem using Elimination Technique:

Some observations are based on elimination technique (Refer to Polya’s How to Solve It book). 

  • If A knows B, then A can’t be a celebrity. Discard A, and B may be celebrity.
  • If A doesn’t know B, then B can’t be a celebrity. Discard B, and A may be celebrity.
  • Repeat above two steps till there is only one person.
  • Ensure the remained person is a celebrity. (What is the need of this step?)

Follow the steps below to solve the problem:

  • Create a stack and push all the ids in the stack.
  • Run a loop while there are more than 1 element in the stack.
  • Pop the top two elements from the stack (represent them as A and B)
  • If A knows B, then A can’t be a celebrity and push B in the stack. Else if A doesn’t know B, then B can’t be a celebrity push A in the stack.
  • Assign the remaining element in the stack as the celebrity.
  • Run a loop from 0 to n-1 and find the count of persons who knows the celebrity and the number of people whom the celebrity knows.
    • If the count of persons who knows the celebrity is n-1 and the count of people whom the celebrity knows is 0 then return the id of the celebrity else return -1.

Below is the implementation of the above approach:

C++
// C++ program to find celebrity
#include <bits/stdc++.h>
#include <list>
using namespace std;

// Max # of persons in the party
#define N 8

// Person with 2 is celebrity
bool MATRIX[N][N] = { { 0, 0, 1, 0 },
                      { 0, 0, 1, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 1, 0 } };

bool knows(int a, int b) { return MATRIX[a][b]; }

// Returns -1 if celebrity
// is not present. If present,
// returns id (value from 0 to n-1).
int findCelebrity(int n)
{

    stack<int> s;

    // Celebrity
    int C;

    // Push everybody to stack
    for (int i = 0; i < n; i++)
        s.push(i);

    // Extract top 2

    // Find a potential celebrity
    while (s.size() > 1) {
        int A = s.top();
        s.pop();
        int B = s.top();
        s.pop();
        if (knows(A, B)) {
            s.push(B);
        }
        else {
            s.push(A);
        }
    }

    // Potential candidate?
    C = s.top();
    s.pop();

    // Check if C is actually
    // a celebrity or not
    for (int i = 0; i < n; i++) {
        // If any person doesn't
        // know 'C' or 'C' doesn't
        // know any person, return -1
        if ((i != C) && (knows(C, i) || !knows(i, C)))
            return -1;
    }

    return C;
}

// Driver code
int main()
{
    int n = 4;
    int id = findCelebrity(n);
    id == -1 ? cout << "No celebrity"
             : cout << "Celebrity ID " << id;
    return 0;
}
Java
// Java program to find celebrity using
// stack data structure
import java.util.Stack;

class GFG {
    // Person with 2 is celebrity
    static int MATRIX[][] = { { 0, 0, 1, 0 },
                              { 0, 0, 1, 0 },
                              { 0, 0, 0, 0 },
                              { 0, 0, 1, 0 } };

    // Returns true if a knows
    // b, false otherwise
    static boolean knows(int a, int b)
    {
        boolean res = (MATRIX[a][b] == 1) ? true : false;
        return res;
    }

    // Returns -1 if celebrity
    // is not present. If present,
    // returns id (value from 0 to n-1).
    static int findCelebrity(int n)
    {
        Stack<Integer> st = new Stack<>();
        int c;

        // Step 1 :Push everybody
        // onto stack
        for (int i = 0; i < n; i++) {
            st.push(i);
        }

        while (st.size() > 1) {
            // Step 2 :Pop off top
            // two persons from the
            // stack, discard one
            // person based on return
            // status of knows(A, B).
            int a = st.pop();
            int b = st.pop();

            // Step 3 : Push the
            // remained person onto stack.
            if (knows(a, b)) {
                st.push(b);
            }

            else
                st.push(a);
        }

        // If there are only two people
        // and there is no
        // potential candidate
        if (st.empty())
            return -1;

        c = st.pop();

        // Step 5 : Check if the last
        // person is celebrity or not
        for (int i = 0; i < n; i++) {
            // If any person doesn't
            //  know 'c' or 'a' doesn't
            // know any person, return -1
            if (i != c && (knows(c, i) || !knows(i, c)))
                return -1;
        }
        return c;
    }

    // Driver Code
    public static void main(String[] args)
    {
        int n = 4;
        int result = findCelebrity(n);
        if (result == -1) {
            System.out.println("No Celebrity");
        }
        else
            System.out.println("Celebrity ID " + result);
    }
}

// This code is contributed
// by Rishabh Mahrsee
Python
# Python3 program to find celebrity
# using stack data structure

# Max # of persons in the party
N = 8

# Person with 2 is celebrity
MATRIX = [[0, 0, 1, 0],
          [0, 0, 1, 0],
          [0, 0, 0, 0],
          [0, 0, 1, 0]]


def knows(a, b):

    return MATRIX[a][b]

# Returns -1 if celebrity
# is not present. If present,
# returns id (value from 0 to n-1).


def findCelebrity(n):

    # Handle trivial
    # case of size = 2
    s = []

    # Push everybody to stack
    for i in range(n):
        s.append(i)

    # Find a potential celebrity
    while (len(s) > 1):

          # Pop out the first two elements from stack
        A = s.pop()
        B = s.pop()

        # if A knows B, we find that B might be the celebrity and vice versa
        if (knows(A, B)):
            s.append(B)
        else:
            s.append(A)

    # If there are only two people
    # and there is no
    # potential candidate
    if(len(s) == 0):
        return -1

    # Potential candidate?
    C = s.pop()

    # Last candidate was not
    # examined, it leads one
    # excess comparison (optimize)
    if (knows(C, B)):
        C = B

    if (knows(C, A)):
        C = A

    # Check if C is actually
    # a celebrity or not
    for i in range(n):

        # If any person doesn't
        # know 'a' or 'a' doesn't
        # know any person, return -1
        if ((i != C) and
            (knows(C, i) or
                not(knows(i, C)))):
            return -1

    return C


# Driver code
if __name__ == '__main__':

    n = 4
    id_ = findCelebrity(n)

    if id_ == -1:
        print("No celebrity")
    else:
        print("Celebrity ID ", id_)

# This code is contributed by UnworthyProgrammer
C#
// C# program to find celebrity using
// stack data structure
using System;
using System.Collections.Generic;

public class GFG {
    // Person with 2 is celebrity
    static int[, ] MATRIX = { { 0, 0, 1, 0 },
                              { 0, 0, 1, 0 },
                              { 0, 0, 0, 0 },
                              { 0, 0, 1, 0 } };

    // Returns true if a knows
    // b, false otherwise
    static bool knows(int a, int b)
    {
        bool res = (MATRIX[a, b] == 1) ? true : false;
        return res;
    }

    // Returns -1 if celebrity
    // is not present. If present,
    // returns id (value from 0 to n-1).
    static int findCelebrity(int n)
    {
        Stack<int> st = new Stack<int>();
        int c;

        // Step 1 :Push everybody
        // onto stack
        for (int i = 0; i < n; i++) {
            st.Push(i);
        }

        while (st.Count > 1) {
            // Step 2 :Pop off top
            // two persons from the
            // stack, discard one
            // person based on return
            // status of knows(A, B).
            int a = st.Pop();
            int b = st.Pop();

            // Step 3 : Push the
            // remained person onto stack.
            if (knows(a, b)) {
                st.Push(b);
            }

            else
                st.Push(a);
        }

        // If there are only two people
        // and there is no
        // potential candidate
        if (st.Count == 0)
            return -1;

        c = st.Pop();

        // Step 5 : Check if the last
        // person is celebrity or not
        for (int i = 0; i < n; i++) {
            // If any person doesn't
            //  know 'c' or 'a' doesn't
            // know any person, return -1
            if (i != c && (knows(c, i) || !knows(i, c)))
                return -1;
        }
        return c;
    }

    // Driver Code
    public static void Main(String[] args)
    {
        int n = 4;
        int result = findCelebrity(n);
        if (result == -1) {
            Console.WriteLine("No Celebrity");
        }
        else
            Console.WriteLine("Celebrity ID " + result);
    }
}

// This code is contributed by umadevi9616
Javascript
// javascript program to find celebrity using
// stack data structure
    // Person with 2 is celebrity
    var MATRIX = [ [ 0, 0, 1, 0 ], 
    [ 0, 0, 1, 0 ], 
    [ 0, 0, 0, 0 ], 
    [ 0, 0, 1, 0 ] ];

    // Returns true if a knows
    // b, false otherwise
    function knows(a , b) {
        var res = (MATRIX[a][b] == 1) ? true : false;
        return res;
    }

    // Returns -1 if celebrity
    // is not present. If present,
    // returns id (value from 0 to n-1).
    function findCelebrity(n) {
        var st = new Array();
        var c;

        // Step 1 :Push everybody
        // onto stack
        for (var i = 0; i < n; i++) {
            st.push(i);
        }

        while (st.length > 1)
        {
        
            // Step 2 :Pop off top
            // two persons from the
            // stack, discard one
            // person based on return
            // status of knows(A, B).
            var a = st.pop();
            var b = st.pop();

            // Step 3 : Push the
            // remained person onto stack.
            if (knows(a, b)) {
                st.push(b);
            }

            else
                st.push(a);
        }

        // If there are only two people
        // and there is no
        // potential candidate
        if (st.length==0)
            return -1;

        c = st.pop();

        // Step 5 : Check if the last
        // person is celebrity or not
        for (i = 0; i < n; i++) 
        {
        
            // If any person doesn't
            // know 'c' or 'a' doesn't
            // know any person, return -1
            if (i != c && (knows(c, i) || !knows(i, c)))
                return -1;
        }
        return c;
    }

    // Driver Code    
        var n = 4;
        var result = findCelebrity(n);
        if (result == -1) {
            console.log("No Celebrity");
        } else
            console.log("Celebrity ID " + result);

// This code is contributed by gauravrajput1

Output
Celebrity ID 2

Time Complexity: O(N), The total number of comparisons is 3(N-1).
Auxiliary Space: O(N), n extra space is needed to store the stack.

The Celebrity Problem using Elimination Technique (Efficient):

The idea is to follow below to steps based on the above approach:

  • If A knows B, then A can’t be a celebrity. Discard A, and B may be celebrity.
  • If A doesn’t know B, then B can’t be a celebrity. Discard B, and A may be celebrity.

We will not use any extra space as will use spaces M[i][i] for storing whether i th person is a celebrity or not as these are by default 0, so if we find i th person is not a celebrity then we will mark M[i][i] as 1

Follow the steps below to solve the problem:

  • We will make a variable that will store the current row and start a loop from 0 to n-1 and if M[row][i] is 1 then mark M[row][row]=1 and update row = i and if M[row][i]=0 then mark M[i][i]=1.
  •  After the loop we iterate on the diagonal of the matrix i.e M[i][i] where i->(0,n-1) there will be only one element in the diagonal whose value will be 0, when found iterate on all the rows from top to bottom with the column set to i  and if there is no 0 in that column then return i and if there are positive number of zeroes then return -1

Below is the implementation of the above approach:

C++
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find if there is a celebrity in the party
    // or not.
    int celebrity(int M[4][4], int n)
    {
        // r=row number
        int r = 0;
        for (int i = 1; i < n; i++) {
            // checking if r th person knows i th person
            if (M[r][i] == 1) {
                M[r][r] = 1;
                r = i;
            }
            else {
                M[i][i] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            // checking if i th person can be a celebrity or
            // not
            if (M[i][i] == 0) {
                int flag = 0;
                // iterating in the i th column to check
                // whether everyone knows i th person or not
                for (int j = 0; j < n; j++) {
                    // checking if M[j][i] is not a diagonal
                    // element and if j th person knows i th
                    // person
                    if (j != i && M[j][i] == 0 || M[i][j] == 1) {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0)
                    return i;
            }
        }
        return -1;
    }
};

int main()
{
    int M[4][4] = { { 0, 0, 1, 0 },
                    { 0, 0, 1, 0 },
                    { 0, 0, 0, 0 },
                    { 0, 0, 1, 0 } };
    Solution ob;
    int a = ob.celebrity(M, 4);
    if (a == -1) {
        cout << "No Celebrity" << endl;
    }
    else {
        cout << "Celebrity ID " << a << endl;
    }
}
// Contributed by Yash Goyal
Java
/*package whatever //do not write package name here */

import java.io.*;

class GFG {
    // Function to find if there is a celebrity in the party
    // or not.
    static int celebrity(int M[][], int n)
    {
        // r=row number
        int r = 0;
        for (int i = 1; i < n; i++) {
            // checking if r th person knows i th person
            if (M[r][i] == 1) {
                M[r][r] = 1;
                r = i;
            }
            else {
                M[i][i] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            // checking if i th person can be a celebrity or
            // not
            if (M[i][i] == 0) {
                int flag = 0;
                // iterating in the i th column to check
                // whether everyone knows i th person or not
                for (int j = 0; j < n; j++) {
                    // checking if M[j][i] is not a diagonal
                    // element and if j th person knows i th
                    // person
                    if (j != i && M[j][i] == 0) {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0)
                    return i;
            }
        }
        return -1;
    }

    public static void main(String[] args)
    {
        int M[][] = { { 0, 0, 1, 0 },
                      { 0, 0, 1, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 1, 0 } };

        int a = celebrity(M, 4);
        if (a == -1) {
            System.out.println("No Celebrity");
        }
        else {
            System.out.println("Celebrity ID " + a);
        }
    }
}

// This code is contributed by aadityaburujwale.
Python
# Python code for the above approach


# Function to find if there is a celebrity in the party
# or not.
def celebrity(M, n):
    # r=row number
    r = 0
    for i in range(1, n):
        # checking if r th person knows i th person
        if(M[r][i] == 1):
            M[r][r] = 1
            r = i
        else:
            M[i][i] = 1

    for i in range(n):
        # checking if i th person can be a celebrity or
        # not
        if(M[i][i] == 0):
            flag = 0
            # iterating in the i th column to check
            # whether everyone knows i th person or not
            for j in range(n):
                # checking if M[j][i] is not a diagonal
                # element and if j th person knows i th
                      # person
                if(j != i and M[j][i] == 0):
                    flag = 1
                    break
            if(flag == 0):
                return i

    return -1


M = [[0, 0, 1, 0],
     [0, 0, 1, 0],
     [0, 0, 0, 0],
     [0, 0, 1, 0]]
a = celebrity(M, 4)
if(a is -1):
    print("No Celebrity")
else:
    print("Celebrity ID", a)

# This code is contributed by lokeshmvs21.
C#
// Include namespace system
using System;

public class GFG {

    // Function to find if there is a celebrity in the party
    // or not.
    public static int celebrity(int[, ] M, int n)
    {

        // r=row number
        var r = 0;
        for (int i = 1; i < n; i++) {

            // checking if r th person knows i th person
            if (M[r, i] == 1) {
                M[r, r] = 1;
                r = i;
            }
            else {
                M[i, i] = 1;
            }
        }
        for (int i = 0; i < n; i++) {

            // checking if i th person can be a celebrity or
            // not
            if (M[i, i] == 0) {
                var flag = 0;

                // iterating in the i th column to check
                // whether everyone knows i th person or not
                for (int j = 0; j < n; j++) {

                    // checking if M[j][i] is not a diagonal
                    // element and if j th person knows i th
                    // person
                    if (j != i && M[j, i] == 0) {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0) {
                    return i;
                }
            }
        }
        return -1;
    }
    public static void Main(String[] args)
    {
        int[, ] M = { { 0, 0, 1, 0 },
                      { 0, 0, 1, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 1, 0 } };
        var a = GFG.celebrity(M, 4);
        if (a == -1) {
            Console.WriteLine("No Celebrity");
        }
        else {
            Console.WriteLine("Celebrity ID " + a);
        }
    }
}

// This code is contributed by aadityaburujwale.
Javascript
    // Function to find if there is a celebrity in the party
    // or not.
    function celebrity(M,  n)
    {
        // r=row number
        let r = 0;
        for (let i = 1; i < n; i++) {
            // checking if r th person knows i th person
            if (M[r][i] == 1) {
                M[r][r] = 1;
                r = i;
            }
            else {
                M[i][i] = 1;
            }
        }
        for (let i = 0; i < n; i++) {
            // checking if i th person can be a celebrity or
            // not
            if (M[i][i] == 0) {
                let flag = false;
                // iterating in the i th column to check
                // whether everyone knows i th person or not
                for (let j = 0; j < n; j++) {
                    // checking if M[j][i] is not a diagonal
                    // element and if j th person knows i th
                    // person
                    if (j != i && M[j][i] == 0) {
                        flag = true;
                        break;
                    }
                }
                if (flag == false)
                    return i;
            }
        }
        return -1;
    }



    let M = [ [ 0, 0, 1, 0 ],
              [ 0, 0, 1, 0 ],
              [ 0, 0, 0, 0 ],
              [ 0, 0, 1, 0 ] ];
    
    let a = celebrity(M, 4);
    if (a == -1) {
        console.log( "No Celebrity" );
    }
    else {
        console.log("Celebrity ID "+ a );
    }

// This code is contributed by garg28harsh.

Output
Celebrity ID 2

Time Complexity: O(N), Number of iterations is 3 times i.e 3N so the time complexity is O(N) 
Auxiliary Space: O(1)

The Celebrity Problem using Two-pointer approach:

The idea is to use two pointers, one from start and one from the end. Assume the start person is A, and the end person is B. If A knows B, then A must not be the celebrity. Else, B must not be the celebrity. At the end of the loop, only one index will be left as a celebrity. Go through each person again and check whether this is the celebrity. 
The Two Pointer approach can be used where two pointers can be assigned, one at the start and the other at the end, and the elements can be compared and the search space can be reduced. 
 

Follow the steps below to solve the problem:

  • Create two indices i and j, where i = 0 and j = n-1
  • Run a loop until i is less than j.
  • Check if i knows j, then i can’t be a celebrity. so increment i, i.e. i++
  • Else j cannot be a celebrity, so decrement j, i.e. j–
  • Assign i as the celebrity candidate
  • Now at last check whether the candidate is actually a celebrity by re-running a loop from 0 to n-1  and constantly checking if the candidate knows a person or if there is a candidate who does not know the candidate.
    • Then we should return -1. else at the end of the loop, we can be sure that the candidate is actually a celebrity.

Below is the implementation of the above approach:

C++
// C++ program to find celebrity
// in the given Matrix of people
#include <bits/stdc++.h>
using namespace std;
#define N 4
int celebrity(int M[N][N], int n)
{
    // This function returns the celebrity
    // index 0-based (if any)

    int i = 0, j = n - 1;
    while (i < j) {
        if (M[j][i] == 1) // j knows i
            j--;
        else // j doesnt know i so i cant be celebrity
            i++;
    }
    // i points to our celebrity candidate
    int candidate = i;

    // Now, all that is left is to check that whether
    // the candidate is actually a celebrity i.e: he is
    // known by everyone but he knows no one
    for (i = 0; i < n; i++) {
        if (i != candidate) {
            if (M[i][candidate] == 0
                || M[candidate][i] == 1)
                return -1;
        }
    }
    // if we reach here this means that the candidate
    // is really a celebrity
    return candidate;
}

int main()
{
    int M[N][N] = { { 0, 0, 1, 0 },
                    { 0, 0, 1, 0 },
                    { 0, 0, 0, 0 },
                    { 0, 0, 1, 0 } };

    int celebIdx = celebrity(M, 4);

    if (celebIdx == -1)
        cout << ("No Celebrity");
    else {
        cout << "Celebrity ID " << celebIdx;
    }
    return 0;
}

// This code contributed by gauravrajput1
Java
// Java program to find celebrity
// in the given Matrix of people
// Code by Sparsh_cbs

import java.io.*;

class GFG {
    public static void main(String[] args)
    {
        int[][] M = { { 0, 0, 1, 0 },
                      { 0, 0, 1, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 1, 0 } };

        int celebIdx = celebrity(M, 4);

        if (celebIdx == -1)
            System.out.println("No Celebrity");
        else {
            System.out.println("Celebrity ID " + celebIdx);
        }
    }
    public static int celebrity(int M[][], int n)
    {
        // This function returns the celebrity
        // index 0-based (if any)

        int i = 0, j = n - 1;
        while (i < j) {
            if (M[j][i] == 1) // j knows i
                j--;
            else // j doesnt know i so i cant be celebrity
                i++;
        }
        // i points to our celebrity candidate
        int candidate = i;

        // Now, all that is left is to check that whether
        // the candidate is actually a celebrity i.e: he is
        // known by everyone but he knows no one
        for (i = 0; i < n; i++) {
            if (i != candidate) {
                if (M[i][candidate] == 0
                    || M[candidate][i] == 1)
                    return -1;
            }
        }
        // if we reach here this means that the candidate
        // is really a celebrity
        return candidate;
    }
}
Python
# Python3 code
class Solution:

    # Function to find if there is a celebrity in the party or not.
    # return index if celebrity else return -1
    def celebrity(self, M, n):
        # code here
        i = 0
        j = n-1
        candidate = -1
        while(i < j):
            if M[j][i] == 1:
                j -= 1
            else:
                i += 1

        candidate = i
        for k in range(n):
            if candidate != k:
                if M[candidate][k] == 1 or M[k][candidate] == 0:
                    return -1

        return candidate


n = 4
m = [[0, 0, 1, 0],
     [0, 0, 1, 0],
     [0, 0, 0, 0],
     [0, 0, 1, 0]]
ob = Solution()
a = ob.celebrity(m, n)
if a == -1:
    print("No Celebrity")
else:
    print("Celebrity ID", a)
C#
// C# program to find celebrity
// in the given Matrix of people
// Code by Sparsh_cbs
using System;

class GFG {
    public static void Main(String[] args)
    {
        int[, ] M = { { 0, 0, 1, 0 },
                      { 0, 0, 1, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 1, 0 } };

        int celebIdx = celebrity(M, 4);

        if (celebIdx == -1)
            Console.Write("No Celebrity");
        else {
            Console.Write("Celebrity ID " + celebIdx);
        }
    }
    public static int celebrity(int[, ] M, int n)
    {
        // This function returns the celebrity
        // index 0-based (if any)

        int i = 0, j = n - 1;
        while (i < j) {
            if (M[j, i] == 1) // j knows i
                j--;
            else // i knows j
                i++;
        }

        // i points to our celebrity candidate
        int candidate = i;

        // Now, all that is left is to check that whether
        // the candidate is actually a celebrity i.e: he is
        // known by everyone but he knows no one
        for (i = 0; i < n; i++) {
            if (i != candidate) {
                if (M[i, candidate] == 0
                    || M[candidate, i] == 1)
                    return -1;
            }
        }

        // if we reach here this means that the candidate
        // is really a celebrity
        return candidate;
    }
}

// This code is contributed by shivanisinghss2110
Javascript
// JavaScript program to find celebrity
// in the given Matrix of people
// Code by Sparsh_cbs
var M = [ [ 0, 0, 1, 0 ],
                      [ 0, 0, 1, 0 ],
                      [ 0, 0, 0, 0 ],
                      [ 0, 0, 1, 0 ] ];

        var celebIdx = celebrity(M, 4);

        if (celebIdx == -1)
            console.log("No Celebrity");
        else {
            console.log(
                "Celebrity ID " + celebIdx);
        }
    
function celebrity( M, n)
    {
    
        // This function returns the celebrity
        // index 0-based (if any)
        var i = 0, j = n - 1;
        while (i < j) {
            if (M[j][i] == 1) // j knows i
                j--;
            else // i knows j
                i++;
        }
        
        // i points to our celebrity candidate
        var candidate = i;

        // Now, all that is left is to check that whether
        // the candidate is actually a celebrity i.e: he is
        // known by everyone but he knows no one
        for (i = 0; i < n; i++) {
            if (i != candidate) {
                if (M[i][candidate] == 0
                    || M[candidate][i] == 1)
                    return -1;
            }
        }
        
        // if we reach here this means that the candidate
        // is really a celebrity
        return candidate;
  }  
  
 // This code is contributed by shivanisinghss2110 

Output
Celebrity ID 2

Time Complexity: O(N), Iterating two times the array of size N.
Auxiliary Space: O(1) No extra space is required.



Previous Article
Next Article

Similar Reads

The Celebrity Problem | Set-2
In a party of N people, only one person is known to everyone. Such a person may be present at the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in the minimum number of questions.We can describe the problem input as an array of numbers/characters representing p
5 min read
The Celebrity Problem | Set-3
In a party of N people, only one person is known to everyone. Such a person may be present at the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in the minimum number of questions.We can describe the problem input as an array of numbers/characters representing p
4 min read
Secretary Problem (A Optimal Stopping Problem)
The Secretary Problem also known as marriage problem, the sultan's dowry problem, and the best choice problem is an example of Optimal Stopping Problem. This problem can be stated in the following form: Imagine an administrator who wants to hire the best secretary out of n rankable applicants for a position. The applicants are interviewed one by on
12 min read
Transportation Problem | Set 7 ( Degeneracy in Transportation Problem )
Please go through this article first. This article will discuss degeneracy in transportation problem through an explained example. Solution: This problem is balanced transportation problem as total supply is equal to total demand. Initial basic feasible solution: Least Cost Cell Method will be used here to find the initial basic feasible solution.
3 min read
Nuts & Bolts Problem (Lock & Key problem) using Quick Sort
Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently. Constraint: Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means a nut can only be compared with a bolt and a bolt can only be compared with a nut to see which
12 min read
Nuts & Bolts Problem (Lock & Key problem) using Hashmap
Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently. Constraint: Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with a nut to see which one i
5 min read
Difference between 0/1 Knapsack problem and Fractional Knapsack problem
What is Knapsack Problem?Suppose you have been given a knapsack or bag with a limited weight capacity, and each item has some weight and value. The problem here is that "Which item is to be placed in the knapsack such that the weight limit does not exceed and the total value of the items is as large as possible?". Consider the real-life example. Su
13 min read
8 queen problem
The eight queens problem is the problem of placing eight queens on an 8×8 chessboard such that none of them attack one another (no two are in the same row, column, or diagonal). More generally, the n queens problem places n queens on an n×n chessboard. There are different solutions for the problem. Backtracking | Set 3 (N Queen Problem) Branch and
8 min read
The Great Tree-List Recursion Problem.
Asked by Varun Bhatia. Question: Write a recursive function treeToList(Node root) that takes an ordered binary tree and rearranges the internal pointers to make a circular doubly linked list out of the tree nodes. The”previous” pointers should be stored in the “small” field and the “next” pointers should be stored in the “large” field. The list sho
1 min read
Custom Tree Problem
You are given a set of links, e.g. a ---&gt; b b ---&gt; c b ---&gt; d a ---&gt; e Print the tree that would form when each pair of these links that has the same character as start and end point is joined together. You have to maintain fidelity w.r.t. the height of nodes, i.e. nodes at height n from root should be printed at same row or column. For
13 min read