Sunday 29 May 2016

Find the celebrity in the party

There are n people in a party, they might or might not know each others names.

There is one celebrity in the group, celebrity does not know any of n-1 peoples by name and all n people know celebrity by name.

You are given the list of people’s names, You can ask only one question from the people. Do you know this name ?

How many maximum number of questions you need to ask to know the celebrity name?

Note: assume all names are unique. and you know the persons by name(but don’t know if he is celebrity)
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
Answer:
n-1 questions

If we ask a question to a person A about person B that... "Do you know him?"
If person A say yes... then A is not celebrity but B is definitely.
If person A say  no... then A might be a celebrity but B is definitely not a celebrity.

If we are asking this question to everyone in the party, then in worst case when last two persons are remaining then we get our answer.
So (n-1) questions are require to ask.

No comments:

Post a Comment