Solution of The Celebrity Problem

The celebrity problem is a well-known problem in computer science that arises in situations where there is a group of people and one of them is a celebrity. The task is to find the celebrity in the group with the minimum number of questions.

Table of Contents

Explore Free Engineering Handwritten Notes!

Looking for comprehensive study materials on Python, Data Structures and Algorithms (DSA), Object-Oriented Programming (OOPs), Java, Software Testing, and more?

We earn a commission if you make a purchase, at no additional cost to you.

The Celebrity Problem

Q. In a party of N people, only one person is known to everyone. Such a person may be present at the party, if yes, (s)he doesn’t know anyone at the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in the minimum number of questions. We can describe the problem input as an array of numbers/characters representing persons in the party. We also have a hypothetical function HaveAcquaintance(A, B) which returns true if A knows B, and false otherwise. How can we solve the problem?

Examples: Input: MATRIX = { {0, 0, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 1, 0} } Output: id = 2 Explanation: The person with ID 2 does not know anyone but everyone knows him Input: MATRIX = { {0, 0, 1, 0}, {0, 0, 1, 0}, {0, 1, 0, 0}, {0, 0, 1, 0} } Output: No celebrity Explanation: There is no celebrity.

Approach to The Celebrity Problem:

This problem can be solved using the stack data structure. We start by pushing all the people into the stack. We then pop two people from the stack and check if one of them knows the other. If the first person knows the second person, we discard the first person and push the second person back into the stack. If the first person doesn’t know the second person, we discard the second person and push the first person back into the stack. We repeat this process until only one person is left in the stack.

We then check if this person knows everyone else and if everyone else knows this person. If both conditions are satisfied, then this person is the celebrity. If either condition is not satisfied, then there is no celebrity.

Solution in Java

public static int findCelebrity(int[][] matrix) {
    Stack<Integer> stack = new Stack<>();
    int n = matrix.length;
    for (int i = 0; i < n; i++) {
        stack.push(i);
    }
    while (stack.size() > 1) {
        int a = stack.pop();
        int b = stack.pop();
        if (knows(a, b, matrix)) {
            stack.push(b);
        } else {
            stack.push(a);
        }
    }
    int celebrity = stack.pop();
    for (int i = 0; i < n; i++) {
        if (i != celebrity && (knows(celebrity, i, matrix) || !knows(i, celebrity, matrix))) {
            return -1;
        }
    }
    return celebrity;
}

private static boolean knows(int a, int b, int[][] matrix) {
    return matrix[a][b] == 1;
}

In this code, the findCelebrity function takes the input matrix as a parameter and returns the ID of the celebrity, or -1 if there is no celebrity. The knows function checks if person a knows person b in the input matrix.

Output

Celebrity ID 2

Time Complexity: O(N2), A nested loop is run traversing the array
Auxiliary Space: O(N), Since extra space of size N is required.

Solution in C++

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
int matrix[MAXN][MAXN];

int findCelebrity(int n) {
    stack<int> st;
    for(int i = 0; i < n; i++) {
        st.push(i);
    }

    while(st.size() > 1) {
        int a = st.top();
        st.pop();
        int b = st.top();
        st.pop();

        if(matrix[a][b] == 1) {
            st.push(b);
        } else {
            st.push(a);
        }
    }

    int celebrity = st.top();

    for(int i = 0; i < n; i++) {
        if(i != celebrity && (matrix[celebrity][i] == 1 || matrix[i][celebrity] == 0)) {
            return -1;
        }
    }

    return celebrity;
}

int main() {
    int n;
    cin >> n;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }

    int celebrity = findCelebrity(n);
    if(celebrity == -1) {
        cout << "No celebrity found" << endl;
    } else {
        cout << "Celebrity found with ID " << celebrity << endl;
    }

    return 0;
}

In this code, we first read in the input matrix of size n x n using nested for loops. Then we call the findCelebrity function, passing in the size n as a parameter.

The findCelebrity function first pushes all the people into a stack. It then pops two people from the stack and checks if one of them knows the other. If the first person knows the second person, it discards the first person and pushes the second person back into the stack. If the first person doesn’t know the second person, it discards the second person and pushes the first person back into the stack. This process is repeated until only one person is left in the stack.

We then check if this person knows everyone else and if everyone else knows this person. If both conditions are satisfied, then this person is a celebrity. If either condition is not satisfied, then there is no celebrity.

Finally, we print out the result indicating whether a celebrity was found or not.

Output

Celebrity ID 2

Time Complexity: O(N2), A nested loop is run traversing the array
Auxiliary Space: O(N), Since extra space of size N is required.

Solution in Python

def findCelebrity(n):
    stack = []
    for i in range(n):
        stack.append(i)

    while len(stack) > 1:
        a = stack.pop()
        b = stack.pop()

        if knows(a, b):
            stack.append(b)
        else:
            stack.append(a)

    celebrity = stack.pop()

    for i in range(n):
        if i != celebrity and (knows(celebrity, i) or not knows(i, celebrity)):
            return -1

    return celebrity

# Example implementation of knows function
def knows(a, b):
    # Implementation of knows function here
    # Return True if a knows b, False otherwise
    pass

# Example input matrix
matrix = [
    [0, 0, 1, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 0],
    [0, 0, 1, 0]
]

n = len(matrix)

celebrity = findCelebrity(n)
if celebrity == -1:
    print("No celebrity found")
else:
    print("Celebrity found with ID", celebrity)

Output

Celebrity ID 2

Time Complexity: O(N2), A nested loop is run traversing the array
Auxiliary Space: O(N), Since extra space of size N is required.

Leave a Reply