The Celebrity Problem | Java program to find celebrity ; Max # of persons in the party ; Person with 2 is celebrity ; Returns - 1 if celebrity is not present . If present , returns id ( value from 0 to n - 1 ) . ; the graph needs not be constructed as the edges can be found by using knows function degree array ; ; query for all edges ; set the degrees ; find a person with indegree n - 1 and out degree 0 ; Driver code
import java . util . * ; class GFG { static final int N = 8 ; static int MATRIX [ ] [ ] = { { 0 , 0 , 1 , 0 } , { 0 , 0 , 1 , 0 } , { 0 , 0 , 0 , 0 } , { 0 , 0 , 1 , 0 } } ; static int knows ( int a , int b ) { return MATRIX [ a ] [ b ] ; } static int findCelebrity ( int n ) { int [ ] indegree = new int [ n ] ; int [ ] outdegree = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { int x = knows ( i , j ) ; outdegree [ i ] += x ; indegree [ j ] += x ; } } for ( int i = 0 ; i < n ; i ++ ) if ( indegree [ i ] == n - 1 && outdegree [ i ] == 0 ) return i ; return - 1 ; } public static void main ( String [ ] args ) { int n = 4 ; int id = findCelebrity ( n ) ; if ( id == - 1 ) System . out . print ( " No ▁ celebrity " ) ; else System . out . print ( " Celebrity ▁ ID ▁ " + id ) ; } }