Python Program to Solve the Celebrity Problem

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

1. We initialize a stack and push all people onto the stack.
2. 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.
3. After this loop, we have a potential celebrity left on the stack.
4. We validate if the potential celebrity is indeed a celebrity by checking if they know nobody and everybody knows them.
5. If the potential celebrity is valid, we return their ID; otherwise, we return -1.

Input/Output