{"id":9209,"date":"2022-08-29T12:49:37","date_gmt":"2022-08-29T12:49:37","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9209"},"modified":"2023-11-27T12:27:46","modified_gmt":"2023-11-27T12:27:46","slug":"the-celebrity-problem","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/the-celebrity-problem\/","title":{"rendered":"The Celebrity Problem"},"content":{"rendered":"

\"\"<\/p>\n

TThe Celebrity Problem in Java is a classic algorithmic puzzle that challenges programmers to efficiently identify a special individual within a group who is known by everyone but knows no one. This intriguing problem finds its applications in various fields, from network analysis to social media and even in real-world scenarios involving influential figures. As coders strive to devise optimal solutions to this problem, they encounter complexities that illuminate key concepts in algorithm design, graph theory, and computational efficiency.<\/p>\n

Exploring the depths of the Celebrity Problem not only sharpens coding skills but also underscores the significance of problem-solving approaches and their practical implications. In this article, we will delve into the intricacies of the Celebrity Problem, examine different strategies to solve it, and understand its relevance in the realm of programming and beyond.<\/p>\n

What is the Celebrity Problem in Java?<\/h2>\n

There is a party of N (numbered 0 to N-1) people. There might or might not be a celebrity at this party. A celebrity is someone who is known to everyone but does not know anyone. So, if you are a celebrity at a party, you will be known to everyone, but you won\u2019t know anyone there.<\/p>\n

This situation is represented in the form of an N x N binary matrix.<\/a> So, every cell can either have a value of 0 or 1. If matrix[i][j] = 1, this means that the ith person knows the jth person.<\/p>\n

You have to tell whether a celebrity is present at the party or not. If it is present, we also have to tell which element (person) is the celebrity.<\/p>\n

Note:<\/strong> The elements of the diagonal, i.e., when i = j, are always set to 0.<\/p>\n

Example of the Celebrity Problem<\/h3>\n

Let us consider the binary matrix shown below.<\/p>\n

\"\"<\/p>\n

So, in the above matrix, 1 is the celebrity. This is because the row with index 1 has all elements 0 which means that 1 does not know anyone and the column with index 1 has all the elements 1 (except where row=column=1) which means that every element (every person in the party) knows 1. Let us consider some more examples.<\/p>\n

\"\"<\/p>\n

In the above matrix, there is a column (column 1) that has all the elements 1 (except row=col); however, row 1 has a 1 in it at column 2. This means that 1 knows 2. So, 1 cannot be a celebrity. In fact, there is no celebrity in the matrix.<\/p>\n

\"\"<\/p>\n

In another case, when we have row = 1, all the elements are 0. However, in this case, column = 1 does not have all the elements 1. The element at row = 2 is 0, meaning 2 does not know 1. Hence, 1 cannot be a celebrity. In fact, there is no celebrity in this matrix.<\/p>\n

How many Celebrities are possible in a Matrix?<\/h3>\n

Before we jump into solving the problem, a very genuine question to ask is the minimum and maximum number of celebrities possible in a matrix. Consider the matrix shown below.<\/p>\n

\"\"<\/p>\n

So, in the above matrix, there is no row with all elements 0 and, similarly, no column with all values 1 (except where row=col). As a result, the bare minimum of celebrities is 0.
\nAssume there are two celebrities in the matrix, X and Y. As a result, according to the definition of celebrity,<\/p>\n

    \n
  1. Because X is a celebrity, X should not know Y, and Y should know X.<\/li>\n
  2. Because Y is a celebrity, Y should not know X, and X should know Y.<\/li>\n<\/ol>\n

    Statement 1 states that X should not know Y, while Statement 2 states that S should know Y. These statements are diametrically opposed. Our assumption that there are 2 celebrities in the matrix is never possible.<\/p>\n

    So, the maximum number of celebrities possible in a matrix is 1.<\/strong><\/p>\n

    Basic Approach to Solve the Celebrity Problem<\/h3>\n

    The basic approach is actually very intuitive. Let us represent the people in the party with the help of the vertices (nodes) of a graph. An edge from vertex V1 to V2 means V1 knows V2.<\/p>\n

    \"\"<\/p>\n

    Now, consider the matrix that is shown below and the graph corresponding to it.<\/p>\n

    \"\"<\/p>\n

    So, in the matrix, we can see that matrix[0][1] = 1 and matrix[0][2] = 1. This means that 0 knows 1 and 2. This is shown in the graph by the directed edges from vertex 0 to vertices 1 and 2 respectively.<\/p>\n

    Similarly, the entire graph is created by traversing the matrix once. So, a celebrity in this case will be a vertex whose indegree is V-1 (everyone knows the celebrity), where V is the total number of vertices, and whose outdegree is 0 (the celebrity knows no one).<\/p>\n

    So, instead of constructing an actual graph, we can have two arrays of size V representing the indegree and outdegree of each vertex, respectively. So, let us consider the situation shown below.<\/p>\n

    \"\"<\/p>\n

    So, we have 2 arrays, in and out for the matrix. As shown, initially, they are filled with 0s. Now, let us traverse the 1st row of the matrix.<\/p>\n

    \"\"<\/p>\n

    Since matrix[0][0] = 0, this means that currently, there is no edge. Since diagonal elements are 0, there will not be any self-loops in the graph.<\/strong><\/p>\n

    Now, let us move to the next index. <\/p>\n

    \"\"<\/p>\n

    Since matrix[0][1] = 1, this means that there should be an edge from 0 to 1. This means that the outdegree of 0 should increase by 1 and the in-degree of 1 should increase by 1. So, the conclusion that we derive from this is shown below.<\/p>\n

    \"\"<\/p>\n

    So, we can traverse the entire matrix and fill the array<\/a> using this condition.<\/p>\n

    \"\"<\/p>\n

    Now, just traverse the arrays and find if for any vertex i, in[i] = V-1 and out[i] = 0. If found, this vertex will be the celebrity.
    \nIn this case, it is vertex 1.<\/p>\n

    Now that we have understood this method, let us write the code for it.<\/p>\n

    Code Implementation of the Celebrity Problem in Java<\/h3>\n\t\t\t\t\t\t