Hello Everyone,
In a party of N people, only one person is known to everyone. Such a person may be present in 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 persons in the party. We also have a hypothetical function HaveAcquaintance(A, B) which returns true if A knows B, 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.
We measure the complexity in terms of calls made to HaveAcquaintance().
Method 1: This uses Graph to arrive at the particular solution.
Approach:
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.
Algorithm:
- 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
Implementation:
// 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;
}
Output :
Celebrity ID 2
Complexity Analysis:
-
Time Complexity: O(n2).
A nested loop is run traversing the array, SO the time complexity is O(n2) -
Space Complexity: O(n).
Since extra space of size n is required.
Approach :
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 use Recursion to find the potential celebrity among n persons, 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.
Algorithm :
- 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 first n-1 elements does not know n-1 then return id of 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.
Implementation:
// 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;
}
Output :
Celebrity ID 2
Complexity Analysis:
-
Time Complexity: O(n).
The recursive function is called n times, so the time complexity is O(n). -
Space Complexity: O(1).
As no extra space is required.