Every question can eliminate 1 person so you can identify the spy in N-1 questions.
Bhavesh On 19 December 2010 23:46, Dave <[email protected]> wrote: > Here is an algorithm: > > spy = 1 > for i = 2 to N do > if person[spy] knows person[i] > then person[i] is not the spy. > else if person[i] knows person[spy] > then person[spy] is not the spy, set spy = i > end if > end for > for i = 1 to spy-1 do > if (person[spy] does not know person[i]) or (person[i] knows > person[spy]) > then there is no spy, set spy = undefined, break > end if > end for > > If there is a spy, you find him in at least 2*N - 2 questions and at > most 4*N - 4 questions. > > Dave > > On Dec 19, 8:01 am, snehal jain <[email protected]> wrote: > > There is a city of N people. The government learnt that some > > unfriendly nation planted a spy there. A spy possesses unique > > characteristics: he knows everybody in the city, but nobody knows him. > > > > You are a counteragent sent by the government to catch the spy. You > > may ask the people in the city only one question: "Do you know the > > person X?" You may ask as many people as you wish, and one person may > > be asked as many times as you wish. All the people, including the spy, > > always answer honestly. > > > > How many questions you need to find out who is the spy? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
