Java program to solve Celebrity Problem using stack

Hello Everyone! In this Java tutorial, we are going to discuss the problem of a celebrity program using a stack. We are going to use the stack method to solve this problem in Java.

How to solve the Celebrity problem in Java?

First, understand what is climb stair problem. In this problem, A superstar is someone who doesn’t recognize everybody but everyone recognizes him. In another word, We need to locate find the celebrity among a group of people on the basis of his/her popularity. A celebrity is a person who’s widely known to all people the various group. A superstar is someone who doesn’t recognize everybody (along with themselves) however is understood by means of each person. The hassle is to locate who the movie star is via asking humans questions of the form, “Do you know x?”. There are some conditions/regulations with the aid of which we are capable of discover the celebrity. The conditions/rules which follows:-. The conditions/rules which follows:-

• You are given a number n, representing the number of people in Array.
• Everyone in the group must know the celebrity.
• Celebrity does not know anyone in the group.
• The celebrity does not know himself/herself.
• The maximum variety of celebrities a number of the institution is one.
• A celebrity is characterized as someone who knows no other individual than himself except for every other person knows him.

Java code for solving the celebrity problem

import java.util.Scanner;
import java.util.Stack;

public class Elements
{
    private static final Scanner sc = new Scanner(System.in);

    public static void main(String[] args) 
       {
        
        //int[][] arr={{0,0,0,0},{1,0,1,1},{1,1,0,1},{1,1,1,0}};
        System.out.println("Enter the size of the Array:- ");
        int n = sc.nextInt();
        int[][] arr = new int[n][n];

        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                arr[j][k] = sc.nextInt();
            }
        }
        sc.close();

        Stack<Integer> obj = new Stack<>();
        
        for(int i =0;i<arr.length;i++)
        {
            obj.push(i);
        }
        
        while(obj.size()>=2)
        {
            int i=obj.pop();
            int j=obj.pop();
            
            if(arr[i][j]==0)
            {
                obj.push(i);
            }
            else
            {
                obj.push(j);
            }
        }
        int pos=obj.pop();
        for(int i=0;i<arr.length;i++)
        {
            if(i!=pos)
            {
                if(arr[i][pos]==0||arr[pos][i]==1)
                {
                    System.out.println("None");
                    return;
                }
            }
        }
        System.out.println("Celebrity :- "+pos);
    }
}

Implementation using Stack

• If the Stack is empty(which it’s far first of all), then push the element in it.
• Then take the two-element from the stack & put them in the array index then compare whether the result is 1 & 0 put in the stack according to if/else conditions.
• Run a loop while there are more than 1 element inside the stack.
• Pop-top two-element from the stack (constitute them as A and B).
• If A knows B, then A can’t be a superstar and push B in the stack. Else if A doesn’t recognize B, then B can’t be a celeb push A in the stack.
• Assign the closing detail in the stack as the celebrity.
• Run a loop from 0 to n-1 and find the count of people who knows the superstar and the number of humans whom the celeb knows.
• If the depend on individuals who know the superstar is n-1 and the remember of people whom the superstar knows is zero then print the identity of superstar else print “None”.

 

Now, run this program see the output.

Case 1

Input

Enter the size of the Array:- 5
0 0 1 1 1
1 0 1 1 1
1 1 0 1 1
0 0 0 0 0
1 0 1 1 0

Output

Celebrity:- 3

In this case, 4 row is our celebrity.

Case 2

Input

Enter the size of the Array:- 5
0 0 1 1 1
1 0 1 1 1
1 1 0 1 1
0 1 0 0 1
1 0 1 1 0

Output

None

In this case, no one is a celebrity.

Now, You can understand how to solve the Celebrity problem.

Also read: Flood Fill Problem using recursion in Java