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.

- Python File Methods
- Python program to add digits of a number
- Python program for subset sum problem
- Generating strong password using Python
- Download Google Images using Python Script
- Python examples on simple mathematical problems
- Program for adding two binary numbers
- Python Program to Solve n-Queen Problem with Recursion
- Python Program to Solve n-Queen Problem without Recursion
- Python Programs on Games

We use cookies to ensure that we give you the best experience on our website. If you continue to use this site we will assume that you are happy with it.Ok