Survivor Challenge
I am working on a survivor problem as below: Here is the source
Full Question Text: Take a second to imagine that you are in a room with 100 chairs arranged in a circle. These chairs are numbered sequentially from one to one hundred.
At some point in time, the person in chair # 1 will be asked to leave the room. The person in chair number 2 will be admitted, and the person in chair number 3 will go away. Nearby is a man in chair # 6. In other words, 1 person will be skipped initially, and then 2, 3, 4 .. and so on. This skip scheme will continue around the circle until there is only one person left ... a survivor. Note that the chair is removed when the person leaves the room.
Write a program to find out where the survivor is.
Below is the code:
public class ChairProblem {
public static void main(String[] args) {
System.out.println(getSurvivors(100));
}
private static int getSurvivors(int numChairs) {
if (numChairs < 1) {
return -1;
}
// populate chair array list
ArrayList<Integer> chairs = new ArrayList<Integer>();
for (int i = 0; i < numChairs; i++) {
chairs.add(i + 1);
}
// removing all but one elements
int indexOfChair = 0;
while (chairs.size() > 1) {
chairs.remove(indexOfChair);
indexOfChair++;// skip every other chair
indexOfChair %= chairs.size();// loop to beginning if necessary
}
return chairs.get(0);
}
}
My above method does not preempt # 1, then # 3, and then # 6 as described in the requirements. Can anyone help me with this?
My answer is that you enter a second say variable of count
type int after indexOfChair
and initialize 1. Now in the loop while
instead of indexOfChair++
using indexOfChair += count;
, then you increment count
by 1. As shown below:
int indexOfChair = 0;
int count = 1;
while (chairs.size() > 1) {
chairs.remove(indexOfChair);
indexOfChair += count;// skip the count number of chairs
count++; //increase the number of chairs to skip by 1
indexOfChair %= chairs.size();// loop to beginning if necessary
}
You are evaluating the wrong indexOfChair code. The position of the last remote chair is lost at each iteration. You have to keep the last removed chair position and add the added indexOfChair to it.
The problem is similar to that of Joseph. It may be easier to use a recursive strategy: make the first exception and apply the algorithm recursively to the remaining group. Something like:
findSurvivor(int start, int skip, ArrayList<Integer> chairs)
if chairs contains one element declare winner and return
else findSurvivor((start+skip)%(chairs.size()-1), skip+1, chairs with start removed)