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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
