This Python program solves the Celebrity Problem by finding a person who is known by everyone but does not know anyone in return. In the Celebrity Problem, you are given a group of people at a party, and you need to find out who the celebrity is. A celebrity is defined as someone who knows nobody in the group, but everybody else in the group knows them. We can solve this problem efficiently using a stack-based algorithm.

## Problem Statement

You are given a list of people at a party, represented by their IDs (integers from 0 to N-1), where N is the number of people. You are also given a function `knows(a, b)`

that returns True if person ‘a’ knows person ‘b’, and False otherwise. Write a Python program to find the celebrity in the group, or determine that there is no celebrity.

## Python Program to Solve the Celebrity Problem

def find_celebrity(N): stack = [] # Push all people onto the stack for i in range(N): stack.append(i) while len(stack) > 1: a = stack.pop() b = stack.pop() if knows(a, b): # If 'a' knows 'b', 'a' cannot be the celebrity stack.append(b) else: # If 'a' doesn't know 'b', 'b' cannot be the celebrity stack.append(a) potential_celebrity = stack.pop() # Check if the potential celebrity is indeed a celebrity for i in range(N): if i != potential_celebrity and (knows(potential_celebrity, i) or not knows(i, potential_celebrity)): return -1 # No celebrity found return potential_celebrity # Example function 'knows' (replace with your own implementation) def knows(a, b): # Example: a knows b if 'a' is even and 'b' is odd return a % 2 == 0 and b % 2 == 1 # Replace the 'knows' function with your own implementation # Input N = 4 celebrity = find_celebrity(N) # Output if celebrity != -1: print(f"The celebrity is person {celebrity}") else: print("No celebrity found in the group.")

## How It Works

- We initialize a stack and push all people onto the stack.
- While there are at least two people on the stack, we pop two people (‘a’ and ‘b’) and check if ‘a’ knows ‘b’. If ‘a’ knows ‘b’, we push ‘b’ back onto the stack; otherwise, we push ‘a’ back.
- After this loop, we have a potential celebrity left on the stack.
- We validate if the potential celebrity is indeed a celebrity by checking if they know nobody and everybody knows them.
- If the potential celebrity is valid, we return their ID; otherwise, we return -1.

## Leave a Review