In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he does not know anyone in the party. We can only ask questions like does A know B? . Find the stranger (celebrity) in minimum number of questions.
Problem Statement:
The celebrity problem is the problem of finding the celebrity among n people. A celebrity is someone who doesn’t know anyone (including themselves) but is known by everyone.
Solution:
Python Program to Solve the Celebrity Problem source code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | def eliminate_non_celebrities(matrix): """Take an n x n matrix that has m[i][j] = True iff i knows j and return person who is maybe a celebrity.""" possible_celeb = 0 n = len(matrix) for p in range(1, n): if (matrix[possible_celeb][p] or not matrix[p][possible_celeb]): possible_celeb = p return possible_celeb def check_if_celebrity(possible_celeb, matrix): """Take an n x n matrix that has m[i][j] = True iff i knows j and return True if possible_celeb is a celebrity.""" for i in range(n): if matrix[possible_celeb][i] is True: return False for i in range(n): if matrix[i][possible_celeb] is False: if i != possible_celeb: return False return True n = int(input('Number of people: ')) # create n x n matrix initialized to False that has m[i][j] = True iff i knows j m = [[False]*n for _ in range(n)] for i in range(n): people = input('Enter list of people known to {}: '.format(i)).split() for p in people: p = int(p) m[i][p] = True possible_celeb = eliminate_non_celebrities(m) if check_if_celebrity(possible_celeb, m): print('{} is the celebrity.'.format(possible_celeb)) else: print('There is no celebrity.') |
If you like FreeWebMentor and you would like to contribute, you can write an article and mail your article to [email protected] Your article will appear on the FreeWebMentor main page and help other developers.
