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.
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