Given a group of persons who either know or don’t know each other. If a person is known by everyone from the group but doesn’t know anyone himself then we call him a celebrity. Design and implement an efficient algorithm to find the celebrity by asking the question “does person A know person B” as few times as possible.

Assignment

Write a function findTheCelebrity(group: list) that return the celebrity in a given group; if the group has no celebrity, it returns None.

The group is represented by a matrix. We say that person 0 knows person 1 if group[0][1] == True and that person 0 doesn’t know person 1 if group[0][1] == False A person is a celebrity when it’s entire row consists of True and its entire column consists of False, except on the diagonal squares those contain None.

De correctness of your code will be tested automatically. Think about the efficiency of your code.

Examples

>>> findTheCelebrity([ [None, False], [True, None]])
0
>>> findTheCelebrity([ [None, False, False], [True, None, True], [True, False, None]])
0
>>> findTheCelebrity([ [None, True, False], [False, None, False], [True, True, None]])
1
>>> findTheCelebrity([ [None, False, True], [False, None, True], [False, False, None]])
2
>>> findTheCelebrity([[None, False, False ], [False, None, False], [False, False, None]])