Find the Celebrity
knows(a: int, b: int) -> bool takes time to check if a person is a celebrity.
# Brute Force
Check if each person is a celebrity.
def findCelebrity(self, n): for i in range(n): founded = True for j in range(n): if i == j: continue founded = founded and (knows(j,i) and not knows(i,j)) if founded: return i return -1
# Logical Deduction
Does A know B? If the answer is yes, then A is definitely not a celebrity; otherwise, B is not a celebrity. Thus, we could ask this question
n-1 times and get a
candidate for celebrity.
We then check if:
- everyone else knows the
candidateknows no one else
def findCelebrity(self, n): candidate = 0 for i in range(1,n): if not knows(i,candidate): # OR: if knows(candidate,i): candidate = i # check if candidate is a celebrity for i in range(n): if i == candidate: continue if knows(candidate, i) or not knows(i, candidate): return -1 return candidate