Last Updated: 19 Dec, 2020
The Celebrity Problem
Moderate
Asked in companies
There are ‘N’ people at a party. Each person has been assigned a unique id between 0 to 'N' - 1(both inclusive). A celebrity is a person who is known to everyone but does not know anyone at the party.
Given a helper function ‘knows(A, B)’, It will returns "true" if the person having id ‘A’ know the person having id ‘B’ in the party, "false" otherwise. Your task is to find out the celebrity at the party. Print the id of the celebrity, if there is no celebrity at the party then print -1.
Note:
1. The helper function ‘knows’ is already implemented for you.
2. ‘knows(A, B)’ returns "false", if A doesn't know B.
3. You should not implement helper function ‘knows’, or speculate about its implementation.
4. You should minimize the number of calls to function ‘knows(A, B)’.
5. There are at least 2 people at the party.
6. At most one celebrity will exist.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases. The description of ‘T’ test cases follows.
The first line of each test case contains an integer ‘N’, representing the number of people in the party.
Output format :
For each test case, print an integer representing the id of the celebrity. If there is no celebrity at the party then print -1.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
2 <= N <= 10^4
Where ‘T’ is the total number of test cases, ‘N’ is the number of people at the party.
Time Limit: 1sec
Approaches
This problem can be modelled as a graph problem. Consider a directed graph having ‘N’ nodes numbered from 0 to ‘N’ - 1. If the helper function ‘knows(i, j)’ returns true, then it means that there is a directed edge from node ‘i’ to node ‘j’. We can observe that if the celebrity is present then it is represented by a global sink i.e node that has indegree n-1 and outdegree 0.
- Make two integer arrays ‘INDEGREE’ and ‘OUTDEGREE’ of size ‘N’. And fill both of them by 0. These arrays will represent the indegree and outdegree of each node.
- Run a nested loop where the outer loop ‘i’ ranges from 0 to ‘N’ - 1 and the inner loop ‘j’ ranges from 0 to ‘N’ - 1, and for each pair (i, j) if ‘knows(i, j)’ return true, then increment ‘OUTDEGREE[i]’ by 1 and ‘INDEGREE[j]’ by 1.
- Initialize an integer variable ‘CELEBRITY' = -1.
- Run a loop where ‘i’ ranges from 0 to ‘N’ - 1, and find ‘i’ for which ‘INDEGREE[i]’ is ‘N’ - 1 and ‘OUTDEGREE[i]’ is 0 if such ‘i’ exist then assign ‘CELEBRITY’:= ‘i’, otherwise keep the value of ‘CELEBRITY’ as -1.
- Return ‘CELEBRITY’.
Algorithm is as follows:
- Initialize an integer variable 'CELEBRITY' := -1.
- Run a loop where ‘i’ ranges from 0 to ‘N’ - 1, and check whether the person having id ‘i’ is a celebrity or not. This can be done as follow -:
- Initialize two boolean variables, ‘KNOWANY’ and ‘KNOWNTOALL’.
- Run a loop where ‘j’ ranges from 0 to ‘N’ - 1. If ‘knows(i, j)’ returns false for all ‘j’, then set ‘KNOWANY’:= false
- Run a loop where ‘j’ ranges from 0 to ‘N’ - 1 and if ‘knows(j, i)’ return true for all ‘j’ except when ‘j’ = ‘i’, then set ‘KNOWNTOALL’ := true
- If ‘KNOWANY’ is ‘false’ and ‘KNOWNTOALL’ is ‘true’, then assign ‘CELEBRITY’:= ‘i’ and break the loop.
- Return ‘CELEBRITY’.
Approach: If for any pair (i, j) such that ‘i’!= ‘j’, if ‘knows(i, j)’ returns true, then it implies that the person having id ‘i’ cannot be a celebrity as it knows the person having id ‘j’. Similarly if ‘knows(i, j)’ returns false, then it implies that the person having id ‘j’ cannot be a celebrity as it is not known by a person having id ‘i’. We can use this observation to solve this problem
Algorithm is as follows:
- Create a stack and push all ids in it.
- Run a loop while there are more than one element in the stack and in each iteration do the following-:
- Pop two elements from the stack, let these elements be ‘id1’ and ‘id2’.
- If the person with ‘id1’ knows the person with ‘id2’ i.e ‘knows(id1, id2)’ return true, then the person with ‘id1’ cannot be a celebrity, so push ‘id2’ in the stack.
- Otherwise, if the person with ‘id1’ doesn't know the person with ‘id2’ i.e knows(id1, id2) return false, then the person with ‘id2’ cannot be a celebrity, so push ‘id1’ in the stack.
- Only one id remains in the stack, you need to check whether the person having this id is a celebrity or not, this can be done by running two loops. One checks whether this person is known to everyone or not and another loop will check whether this person knows anyone or not.
- If this person is a celebrity return his id otherwise return -1.
Approach: If for any pair ('i', ‘j’) such that 'i' != ‘j’, If ‘knows(i, j)’ returns true, then it implies that the person having id ‘i’ cannot be a celebrity as it knows the person having id ‘j’. Similarly if ‘knows(i, j)’ returns false, then it implies that the person having id ‘j’ cannot be a celebrity as it is not known by a person having id ‘i’.
So, the Two Pointer approach can be used where two pointers can be assigned, one at the start and the other at the end of the elements to be checked, and the search space can be reduced. This approach can be implemented as follow -:
Algorithm is as follows:
- Initialize two integer variables ‘P’:= 0 and ‘Q’:= 'N' - 1. ‘P’ and ‘Q’ will be two pointers pointing at the start and end of search space respectively.
- Run a while loop till 'P' < ‘Q’ and in each iteration do the following.
- If ‘knows(P, Q)’ returns true, then increment ‘P’ by 1.
- If ‘knows(P, Q)’ returns false, then decrement ‘Q’ by 1.
- Check whether the person having id ‘P’ is a celebrity or not, this can be done by running two loops. One checks whether this person is known to everyone or not and another loop will check whether this person knows anyone or not.
- If a person having id ‘P’ is a celebrity then return ‘P’, otherwise return -1.