## 28 April 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
// 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, 