l
Problem: Celebrity Problem
You are given a list of people, represented by integers from 0 to n-1, where n is the number of people. Each person knows every other person in the list, but there is one celebrity among them who does not know anyone else. You need to find the celebrity, if one exists, or return -1 if there is no celebrity.
You are given a helper function `knows(a, b)` that returns true if person a knows person b, and false otherwise. You can call this function as many times as needed.
Write a function `findCelebrity(n)` that takes an integer n representing the number of people and returns the index of the celebrity, or -1 if no celebrity exists.
Example:
```
Input: n = 4
0 knows 1, 1 knows 2, 2 knows 3, and 3 knows no one
Output: 3
Explanation: Person 3 is the celebrity as they are not known by anyone else.
Input: n = 3
0 knows 1 and 2, 1 knows 0 and 2, and 2 knows 0 and 1
Output: -1
Explanation: There is no celebrity in this case as everyone knows someone.
```
Solve the problem with an efficient algorithm and analyze its time complexity.
Input: n = 4
0 knows 1, 1 knows 2, 2 knows 3, and 3 knows no one
Output: 3
Explanation: Person 3 is the celebrity as they are not known by anyone else.
Input: n = 3
0 knows 1 and 2, 1 knows 0 and 2, and 2 knows 0 and 1
Output: -1
Explanation: There is no celebrity in this case as everyone knows someone.
Contact us for software training, education or development
.png)
0 Comments