# If we go throuh one row, indexes which are 0, we know that those indexes will
ID: 3885633 • Letter: #
Question
# If we go throuh one row, indexes which are 0, we know that those indexes will #never be Celebs( hence marking as N°Celebs), only indexes which are l in that #row, have the possibility( hence marking as possibleCelebs) So we make a list of those possible celeb indexes for that row. (Checking beforehand that it was never visited before, and was not deemed to be a noCeleb once we visit an index we mark it as visited, so that in recursion we dont visit #it again. If it's all 0, we found the celeb. tif all possibleCelebs have been checked, and not was a celeb return-1 Helper Method Recurisve def findCelebRec(adjMatrix, curldx, numChecks,noCelebs,visited): possibleCelebs=[] celeb True visited[curldx] True for index in range (len(adjMatrix[curldx]) num Checks += 1 if adjMatrix[curldx[index]1: celeb False if(not(noCelebs[index and not(visited[index)): possibleCelebs.append(index) else noCelebs[index] True return [curldx,numChecks] result-findCelebRec(adjMatrix,idx.numChecks.noCelebs,visited) if celeb for idx in possibleCelebs: if(result[0]!-1): return result return-1,numChecks] def findCeleb(adjMatrix): noCelebs-[False]"len(adjMatrix[0] visited-False]* len(adjMatrix(01) return findCelebRec(adjMatrix,0,0,noCelebs,visited) adjMatrix ([0,0,1,1], [0,0,0,0], print findCeleb(adjMatrix))Explanation / Answer
We can have following observation.
We can use a stack to verify celebrity.
HaveAcquaintance(A, B) is a function which returns TRUE if A know B else False.
Below code is given in C++ it can be easily translated to python code:
// 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)
{
// Handle trivial case of size = 2
stack<int> s;
int C; // Celebrity
// Push everybody to stack
for (int i=0; i<n; i++)
s.push(i);
// Extract top 2
int A = s.top();
s.pop();
int B = s.top();
s.pop();
// Find a potential celevrity
while (s.size() > 1)
{
if (knows(A, B))
{
A = s.top();
s.pop();
}
else
{
B = s.top();
s.pop();
}
}
// Potential candidate?
C = s.top();
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 (int i = 0; i < n; i++)
{
// If any person doesn't know 'a' or 'a'
// 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;
}
// 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)
{
// Handle trivial case of size = 2
stack<int> s;
int C; // Celebrity
// Push everybody to stack
for (int i=0; i<n; i++)
s.push(i);
// Extract top 2
int A = s.top();
s.pop();
int B = s.top();
s.pop();
// Find a potential celevrity
while (s.size() > 1)
{
if (knows(A, B))
{
A = s.top();
s.pop();
}
else
{
B = s.top();
s.pop();
}
}
// Potential candidate?
C = s.top();
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 (int i = 0; i < n; i++)
{
// If any person doesn't know 'a' or 'a'
// 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;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.