Celebrity Problem

Lecture 155:-Celebrity Problem

The Celebrity Problem is a classic problem often used to illustrate the concept of a directed graph and its applications. In this problem, you are given a group of people numbered from 0 to N-1, where each person knows some other people. However, there is one person (the celebrity) who is known by everyone else but doesn't know anyone.

The task is to find the celebrity, if one exists, or determine that there is no celebrity in the group.

Here's a common approach to solving the Celebrity Problem:

Create a two-dimensional matrix or an array to represent the relationships between people. The element matrix[i][j] (or relation[i][j]) will be 1 if person i knows person j, and 0 otherwise.

Initialize two pointers, A and B, to 0 and N-1, respectively. These pointers will be used to keep track of potential celebrities.

Iterate through the group while A is less than B: a. Check if person A knows person B (i.e., matrix[A][B] is 1). If true, person A cannot be the celebrity, so increment A. b. Otherwise, person A doesn't know person B, so person B cannot be the celebrity, so decrement B.

After the loop, check if person A is the celebrity by verifying that: a. Person A doesn't know anyone else (i.e., matrix[A][i] is 0 for all i except A). b. Everyone else knows person A (i.e., matrix[i][A] is 1 for all i except A).

If the conditions in step 4 are satisfied, person A is the celebrity. Otherwise, there is no celebrity in the group.

Here's a simple C++ implementation of the Celebrity Problem:

cppCopy code

#include <iostream> #include <vector> bool knows(int a, int b) { // Placeholder function that returns true if person 'a' knows person 'b' // You can implement this function according to your input data return true; // Replace with actual implementation } int findCelebrity(int N) { int A = 0; int B = N - 1; while (A < B) { if (knows(A, B)) { A++; } else { B--; } } for (int i = 0; i < N; ++i) { if (i != A && (knows(A, i) || !knows(i, A))) { return -1; // No celebrity found } } return A; // A is the celebrity } int main() { int N = 4; // Number of people int celebrity = findCelebrity(N); if (celebrity != -1) { std::cout << "Celebrity found: Person " << celebrity << std::endl; } else { std::cout << "No celebrity found." << std::endl; } return 0; }

In this implementation, the knows function represents the relationship between two people (i.e., whether one person knows the other). You should replace the placeholder knows function with the actual implementation based on your input data. The findCelebrity function finds the celebrity using the approach described earlier.

Keep in mind that the celebrity problem assumes there is exactly one celebrity, or none at all. If multiple celebrities are possible, this approach won't work as intended.