Learn Programming and technology with ease @ developerpublish.com

HomePythonPython Program to Solve the Celebrity Problem

# 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

### You May Also Like

#### Python Program to Remove Duplicates from a Linked List

In this Python program, we will create a singly linked list and remove duplicate elements from it. A linked list...

#### Python Program to Solve n-Queen Problem with Recursion

This Python program uses a recursive approach to solve the n-Queens problem. It explores all possible combinations of queen placements...

#### Python Program to Find Intersection and Union of Two Linked Lists

In this Python program, we will be implementing the intersection and union operations on two linked lists. Linked lists are...