Can anyone please give me the solution to this problem

general
,
1

There are N people in a room and one of them is a celebrity. In the room everyone knows the celebrity and celebrity doesn’t know anyone in the room. You have 1 question ‘do you know him?’ and you can ask this question N times to anyone in the room. The person to whom you are asking question will reply ‘Yes, I know this guy’ or ‘No, I don’t know this guy’. By asking the same question N times to whoever you want to ask you have to figure out who is celebrity in the room. If A knows B doesn’t mean B knows A.

2

@nickzuck_007

You can find well detailed solution of this problem on the internet but i would like to share the solution with you …

Let us consider that you have N person numbered from 1 to N inclusively and you have only one question to ask A knows B …

Pick up any two person … from the N persons

Lets us say we have picked person number 1 and 2 .(you can pick any two of your choice it will not affect the solution at all).

Two possibilities .

1. 1 knows 2 = True 

Here you can see 1 knows 2 if 1 would have been a celebrity than this should be false . It means 1 is not a celebrity .. you are now left with only N-1 person .

2. 1 knows 2 = false

if this is the case we can claim that 2 is not celebrity because if 2 would have been a celebrity then 1 must know 2 . Here again you are now left with N-1 person.

By asking 1 question you can remove 1 person . you have to ask N-1 questions and you will end up finding the celebrity …

Cheers codechef

Wishing you a very happy new year :smiley:

2 Likes
3

You can find more solution and discussion about this problem over this page …

4
  1. Take 1 person and ask whether he knows other persons, one by one upto (N-1). But once you are getting answer YES. Stop there. Lets say this person is m. Now remove person-1 from the list.
  2. Take m and ask the same Q. If he’s saying he doesn’t know anyone, then m is the celebrity.

In step 1 if you are getting all No… then that person 1 is the celebrity.
In step 2 if you are getting answer YES, then consider that person is n.
Now eliminate m and take n and do the same step.

5

Hello subrat2014

You have not the read the question carefully please read the question again you are only allow to ask this question N times …

6

  1. Take 1 person and ask whether he knows other persons, one by one upto (N-1). But once you are getting answer YES. Stop there. Lets say this person is m. Now remove all the persons before m including person 1 from the list.

If m is the last candidate, then he is the celebrity.
3. if m is not last candidate,
Take m and ask the same Q.
If he’s saying he doesn’t know anyone, then m is the celebrity.

In step 1 if you are getting all No… then that person 1 is the celebrity.

In step 3 if you are getting answer YES,
then repeat the step-1

7

Updated the logic.

8

nice answer…

hey @ma5termind can you tell where can we find more such interview problems, because this one sounds interesting… :slight_smile:

Can you mention links here??

Thank you… :slight_smile: