“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:
The problem would be easier to solve if you used a linked list.
Please google Joseph problem. There is an O(n) time solution, which needs some analysis.
Nice implementation using array. Easy to understand too :)
Post a Comment