O(N) if everybody knows everybody. O(N^2) if there is no such condition. (i.e. Ask for each person to everybody.)
On Mon, Dec 20, 2010 at 9:43 PM, Bhavesh Chauhan <chauhan.bhave...@gmail.com > wrote: > Every question can eliminate 1 person so you can identify the spy in N-1 > questions. > > Bhavesh > > > > On 19 December 2010 23:46, Dave <dave_and_da...@juno.com> 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 <learner....@gmail.com> 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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
