The Celebrity Problem | C ++ program to find celebrity ; Max # of persons in the party ; Person with 2 is celebrity ; Returns - 1 if a ' potential ▁ celebrity ' is not present . If present , returns id ( value from 0 to n - 1 ) . ; base case - when n reaches 0 , returns - 1 since n represents the number of people , 0 people implies no celebrity ( = - 1 ) ; find the celebrity with n - 1 persons ; if there are no celebrities ; if the id knows the nth person then the id cannot be a celebrity , but nth person could be one ; if the nth person knows the id , then the nth person cannot be a celebrity and the id could be one ; if there is no celebrity ; Returns - 1 if celebrity is not present . If present , returns id ( value from 0 to n - 1 ) . a wrapper over findCelebrity ; find the celebrity ; check if the celebrity found is really the celebrity ; check the id is really the celebrity ; if the person is known to everyone . ; Driver code
#include <bits/stdc++.h> NEW_LINE #include <list> NEW_LINE using namespace std ; #define N  8 NEW_LINE 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 ] ; } int findPotentialCelebrity ( int n ) { if ( n == 0 ) return -1 ; int id = findPotentialCelebrity ( n - 1 ) ; if ( id == -1 ) return n - 1 ; else if ( knows ( id , n - 1 ) ) { return n - 1 ; } else if ( knows ( n - 1 , id ) ) { return id ; } return -1 ; } int Celebrity ( int n ) { int id = findPotentialCelebrity ( n ) ; if ( id == -1 ) return id ; else { int c1 = 0 , c2 = 0 ; for ( int i = 0 ; i < n ; i ++ ) if ( i != id ) { c1 += knows ( id , i ) ; c2 += knows ( i , id ) ; } if ( c1 == 0 && c2 == n - 1 ) return id ; return -1 ; } } int main ( ) { int n = 4 ; int id = Celebrity ( n ) ; id == -1 ? cout << " No ▁ celebrity " : cout << " Celebrity ▁ ID ▁ " << id ; return 0 ; }