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?
source to share
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
}
source to share
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)
source to share