Wednesday, April 28, 2010

Find the last person seated around in a circle program/puzzle

This is a programming question asked at one of the class companies. Following is the question

“n” people are seated around in a circle. At each step, the “m”th person is eliminated from the circle. The next iteration continues from the person next to the eliminated person. In the end, there will be only one person remaining. Given “n” and “m”, write a program to find out the person who will be remaining at the end.
int FindWinner(int n, int m)


Me and my roommate both implemented a solution for the above problem one in Java and the other in C++ respectively. Please see the code and the ouput for the above problem below.

Implementation in Java

package brainteasers;

public class FindWinner {
 public static void main(String[] args) {
  FindWinner finder = new FindWinner();
  char winner = finder.findWinner(10,3);
  System.out.println("\nAnd the winner is "+(char)(winner-32)+"!!");
 }
 
 private char findWinner(int n, int m){
  char[] people = getPeople(n);
  boolean[] eliminated = new boolean[n];
  //always start from 1st person
  int remainingGuys = n;
  int current = 0;
  
  while(remainingGuys>1){
   int inkiPinki=0;
   
   while( eliminated[current] || ++inkiPinki != m )
       current = (current+1) % n;
   
   eliminated[current] = true;
   printStatus( eliminated, people );
   remainingGuys--;
   
   while(eliminated[(current+1)%n]){
    current++;
   }
   
   current = (current+1)%n;
  }
  
  System.out.println();
  return people[current];
 }

 private void printStatus(boolean[] eliminated, char[] people) {
  System.out.println();
  for(int i=0;i<eliminated.length;i++){
   char output;
   if(eliminated[i]){
    output = people[i];
   }else{
    output = (char)(people[i] - 32);
   }
   System.out.print(output+" ");
  }
 }

 private char[] getPeople(int n) {
  char[] people = new char[n];
  System.out.println("Participants are...");
  for(int i=0;i<n;i++){
   people[i] = (char)(i+97);
   System.out.print((char)(people[i]-32)+" ");
  }
  System.out.println();
  return people;
 }
}
/*
Participants are...
A B C D E F G H I J 

A B c D E F G H I J 
A B c D E f G H I J 
A B c D E f G H i J 
A b c D E f G H i J 
A b c D E f g H i J 
a b c D E f g H i J 
a b c D E f g h i J 
a b c D e f g h i J 
a b c D e f g h i j 

And the winner is D!!
*/

Implementation in C++

//============================================================================
// Name        : puzzle.cpp
// Author      : Prabhu Jayaraman
// Version     : 0.1
// Copyright   : Free
// Description : Find Last man stand
//============================================================================

#include <iostream>
using namespace std;

int FindWinner(int n, int m)
{
 int a[n];
 for(int i=0;i<n;i++)
 {
  a[i] = 1;
 }
 int e = 0;
 int c = 0;
 for(int i=0;;i++)
 {
  if(e == (n-1))
   break;
  if(a[i%n] == 1)
   c++;
  if(c == m)
  {
   a[i%n] = 0;
   e++;
   c = 0;
  }
 }
 for(int i=0;i<n;i++)
 {
  if(a[i] == 1)
   return i+1;
 }
 return -1;
}

int main()
{
 int x = FindWinner(20,19);
 cout << x << endl;
 return 0;
}

Cheers,
Bragaadeesh

3 comments:

Shashi said...

The problem would be easier to solve if you used a linked list.

Xian Zhang said...

Please google Joseph problem. There is an O(n) time solution, which needs some analysis.

rajkiranrajkumar said...

Nice implementation using array. Easy to understand too :)