The Celebrity Problem | Max ; Person with 2 is celebrity ; Returns - 1 if a potential celebrity is not present . If present , returns id ( value from 0 to n - 1 ) . ; Base case ; Find the celebrity with n - 1 persons ; If there are no celebrities ; if the id knows the nth person then the id cannot be a celebrity , but nth person could be on ; if the id knows the nth person then the id cannot be a celebrity , but nth person could be one ; If there is no celebrity ; Returns - 1 if celebrity is not present . If present , returns id ( value from 0 to n - 1 ) . a wrapper over findCelebrity ; Find the celebrity ; Check if the celebrity found is really the celebrity ; Check the id is really the celebrity ; If the person is known to everyone . ; Driver code
N = 8 NEW_LINE MATRIX = [ [ 0 , 0 , 1 , 0 ] , [ 0 , 0 , 1 , 0 ] , [ 0 , 0 , 0 , 0 ] , [ 0 , 0 , 1 , 0 ] ] NEW_LINE def knows ( a , b ) : NEW_LINE INDENT return MATRIX [ a ] [ b ] NEW_LINE DEDENT def findPotentialCelebrity ( n ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT id_ = findPotentialCelebrity ( n - 1 ) NEW_LINE if ( id_ == - 1 ) : NEW_LINE INDENT return n - 1 NEW_LINE DEDENT elif knows ( id_ , n - 1 ) : NEW_LINE INDENT return n - 1 NEW_LINE DEDENT elif knows ( n - 1 , id_ ) : NEW_LINE INDENT return id_ NEW_LINE DEDENT return - 1 NEW_LINE DEDENT def Celebrity ( n ) : NEW_LINE INDENT id_ = findPotentialCelebrity ( n ) NEW_LINE if ( id_ == - 1 ) : NEW_LINE INDENT return id_ NEW_LINE DEDENT else : NEW_LINE INDENT c1 = 0 NEW_LINE c2 = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( i != id_ ) : NEW_LINE INDENT c1 += knows ( id_ , i ) NEW_LINE c2 += knows ( i , id_ ) NEW_LINE DEDENT DEDENT if ( c1 == 0 and c2 == n - 1 ) : NEW_LINE INDENT return id_ NEW_LINE DEDENT return - 1 NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 4 NEW_LINE id_ = Celebrity ( n ) NEW_LINE if id_ == - 1 : NEW_LINE INDENT print ( " No ▁ celebrity " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Celebrity ▁ ID " , id_ ) NEW_LINE DEDENT DEDENT