Find celebrity in the party

1,488.3K Views

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

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

You are given the list of people’s names(n+1), 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?

Share
Add Comment

  • 1 Answer(s)

    The solution will be N.

    Let’s start with the two person say A, B.
    If A knows B then A can not be a celebrity.
    If A does not know B then B can not be a celebrity.

    So we strike out one name from our list, so on each question we can reject one name.

    When there are only two people left in the list, then we will ask first person, “Do you know the second person ?”. If he says yes then second person is the celebrity and if he says no then the first person is the celebrity.

    Thus we need to ask a maximum of N questions to correctly figure out celebrity name.

    ronret45 Expert Answered on 29th July 2015.
    Add Comment
  • Your Answer

    By posting your answer, you agree to the privacy policy and terms of service.
  • More puzzles to try-