Saturday, February 26, 2011

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

“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)

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 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 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!!
*/

2 comments :

Unknown said...

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

#include
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;
}

Unknown said...

This is the Josephsus Problem. The problem can be solved using this recurrence:
f(n) = (f(n - 1) + m) % n, f(1) = 0


Thanks to Purav to Providing This Recursive function