Innocents and Criminals: Finding Minority Entity

Problem: There are two types of people in a particular city, innocents and criminals. All you know is that innocents are in majority and would like to get rid of criminals and criminals would like to protect themselves from persecution. You can ask any number of questions, with yes/no type answer, from any person in the city. Propose an algorithm which requires asking the minimum number of questions.

Hint: Trivial solution requires asking O(n^2) questions. You can do it in less than 2n questions.

Solution: show

The trivial solution is very simple and is in-fact O(n^2) time algorithm. Round up every person and ask him about the status of everyone else. People with majority vote of criminal are criminals and people with minority vote of criminal are innocents. Following code solves it:

for i = 1 to N
   for j = 1 to N
      if person[i].isCriminal(j)  // doesnt matter if i == j
         vote[j] += 1
      else
         vote[j] -= 1

for j <- 1 to n 
   if vote[j] > 0
      person[j].persecute()

The most efficient algorithm requires asking only 2N-2 questions. The key to solution of this problem lies in the solution to the problem of Finding Majority Element. If we can find one innocent person in the city, then he can label everyone else truthfully. We know for sure that an innocent will tell the truth. Criminals can lie or say truth depending on circumstances.

Assume that we formulate the problem this way. Let us consider a pool of people, who claim to be innocents. Also let us say that we declare that we will pick the first person in the pool to be our innocent man and he will reveal the identity of everyone else. Then definitely both innocents and criminals would try their best to capture the first spot in the pool.

Now, we play a game like this. We choose a person randomly to represent the first person in the pool. Now we select a new person randomly and ask him should the last person inducted in the pool is Innocent. If he says Yes, then we add him to the pool. If he says No then we remove him and the last person from the pool and discard them from further selection. If the pool is empty we select a person not selected previously to get the first spot in the pool.

We repeat the process until we don't have anymore people to consider. The intuition is that even if all Criminals join the pool initially (by lying), then innocents would boot them out as they are in majority. If more innocents join the pool initially then criminals will not be able to boot all innocents out. Hence the first person remaining in the pool is indeed an innocent. We can see this argument working inductively as well.

The following code implements above logic with the help of a stack:

stack.push(person[1])
for i <- 2 to N
   if !stack.isEmpty() && person[i].isCriminal(stack.top())
      stack.pop()
   else
      stack.push(person[i])
return stack.bottom()