约瑟夫环

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 told to leave the room. The person in chair #2 will be skipped, and the person in chair #3 will be told to leave. Next to go is person in chair #6. In other words, 1 person will be skipped initially, and then 2, 3, 4.. and so on. This pattern of skipping will keep going around the circle until there is only one person remaining.. the survivor. Note that the chair is removed when the person leaves the room. Write a program to figure out which chair the survivor is sitting in. Please send us the answer and your working code.

 

Answer: The survivor is sitting in chair# 31.

Solution 1: using array list

public int findSurvivor() {
	int n = 100; // number of chairs
	List<Integer> chairs = new ArrayList<>();
	for(int i=1; i<=n; i++) {
		chairs.add(i);
	}
	int victim = 0; // the index of chair to be removed
    int step = 0;
    while (chairs.size() > 1) {
        chairs.remove(victim);
        victim += ++step;
        victim %= chairs.size();
    }
    return chairs.get(0);
}

 

Solution 2: using linked list

public int findSurvivor() {
	int n = 100; // number of chairs
	List<Integer> chairs = new LinkedList<>();
	for(int i=1; i<=n; i++) {
		chairs.add(i);
	}
    int step = 1;
    Iterator<Integer> itr = chairs.iterator();
    while (chairs.size() > 1) {
    	for (int i = 0; i < step; i++) {
    		if (!itr.hasNext())
    			itr = chairs.iterator();
    		itr.next();
    	}
    	itr.remove();
    	step++;
    }
    return chairs.get(0);
}