Celebrity is the person to whom everyone know but he do not know any person. This problem one of the programing problem that asked in companies
Problem Statement:
You are going to a party of N people and your task is to find a celebrity in the party. Means Celebrity is know by N-1 person in the party of N people.
Solution:
A Square matrix is used to represent the people in the party → if an element of row i
and column j
is set to 1 it means i-th person knows j
else 0.
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.
There are two ways to solve this problem
- Using Stack
- Using Graph
Using Stack
- 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.
Algorithm
- Create a stack and push all the id’s in the stack.
- Run a loop while there are more than 1 element in the stack.
- Pop top two element from the stack (represent them as A and B)
- If A knows B, then A can’t be a celebrity and push B in stack. Else if A doesn’t know B, then B can’t be a celebrity push A in 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 celebrity else return -1.
Code
MATRIX = [[0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 1, 0]] def a_knows_b(a, b): return MATRIX[a][b] def find_celebrity_stack(guestCount): # create a empty array which act as stack stack = [] # push all guest in the stack (means all ids i.e 0 to guest count) for i in range(guestCount): stack.append(i) while len(stack) > 1: # now pick top two guest from stack guestA = stack.pop() guestB = stack.pop() # check guestA knows guestB # if guestA knows guestB then push back guestB into stack else push guestA if a_knows_b(guestA, guestB): stack.append(guestB) else: stack.append(guestA) if not len(MATRIX): return -1 celebrity = stack.pop() # Now verify that last person in the stack is celebrity or not for i in range(guestCount): if i != celebrity and (a_knows_b(celebrity, i) or not a_knows_b(i, celebrity)): return -1 return celebrity print(find_celebrity_stack(len(MATRIX)))
Using Graph
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. 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
Code
MATRIX = [[0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 1, 0]] def a_knows_b(a, b): return MATRIX[a][b] def find_celebrity_graph(guestCount): # create two array for input and outpu of guests with initial value 0 inputA = [0 for x in range(guestCount)] # [0] * guestCount outputA = [0 for x in range(guestCount)] for i in range(guestCount): for j in range(guestCount): if a_knows_b(i, j): # if "a" knows "b" then value for "a" increement by 1 in inputA array # if "b" knows "a" then value for "a" increment by 1 in outputB array outputA[i] = outputA[i] + 1 inputA[j] = inputA[j] + 1 try: # if any index of inputA has value "guestCount - 1" then we will get index of that value # if at that index in outpuA array value should be "0" to qualify index as celebrity if inputA.count(guestCount - 1) == 1: # if (guestCount - 1) is more than 1 then there is no celebrity celebrity = inputA.index(guestCount - 1) if not outputA[celebrity]: return celebrity else: return -1 except Exception as e: return -1 print(find_celebrity_graph(len(MATRIX)))