Categories
Algorithms

Solving Josephus’s Problem using recursion

Josephu’s problem is a violent, albeit a really interesting mathematics’ problem. According to Wikipedia, during the Jewish-Roman wars, a Jewish historian named Flavious Josephus and his 40 soldiers were trapped in a cave fighting the Roman soldiers. When they were about to be captured, they decided that they had rather die than laying down the weapons and surrender to the Romans. Thus, they created a process for this sacrifice.

The process was that they all would sit in a circle and each person will execute the person sitting next to him/her on the left side (the turn moves clockwise), by doing this repeatedly, at the end they will have one person remaining, and that person will commit suicide by stabbing himself.

Allegedly Josephus was the last survivor in this process and he did not kill himself, he surrendered to the Romans and saved himself.

The theoretical problem is that when there are n people, we have to find position p, such that the position p would be last remaining person after m rounds of executions.

Using Induction to find a solution

If you start solving the problem for smaller number of people, you will start seeing a pattern.

Number of SoldiersPosition Josephus should choose
21
33
41
53
65
77
81
93
105
117
129

When n (number of soldiers) is pure power of 2, safe position p = 1.

When n is odd; n can be written as 2m + 1, then the position is m -1

When n is even; p = 2n – 1.

However the whole process can run in multiple loops and number of participants are getting halved by each iteration. Using this logic we can create a program as given below.

public class JosephusProblem {

	public int findLastStandingMan(int participants) {

		if (participants == 1) {
			return 1;
		}

		if (isEven(participants)) {
			return (2 * findLastStandingMan(participants / 2)) - 1;
		} else {
			return (2 * findLastStandingMan(participants / 2)) + 1;
		}

	}

	private boolean isEven(int number) {
		return (number % 2) == 0;
	}

}