Problem: Josephus

Let’s try another queue problem: a counting game played in a circle.

The story behind this problem is a well-known historical anecdote. I do not know how true it is. The ancient Jewish historian and military commander Flavius Josephus (Yosef ben Matityahu) is said to have survived a collective suicide pact during the Siege of Yodfat in 67 CE.

After the Jewish garrison at Yodfat fell, Josephus and 40 of his soldiers hid in an underground cave, with the Roman army under Vespasian all around them. They did not want to be captured, humiliated, or enslaved, so they agreed to die. Each man would be killed by another, in an order set by drawing lots, instead of each man killing himself. They did it this way because their religion forbade suicide, and because the lots kept anyone from backing out of the pact.

Josephus argued against suicide on religious and philosophical grounds, but he gave in when his comrades threatened him. He later wrote that by “chance or the providence of God,” he and one other man were left at the end. Instead of completing the pact, Josephus convinced the other man to surrender with him. That is how he survived.

Centuries later, mathematicians and computer scientists turned this story into a counting-out game, the Josephus Problem I described above. The math version changes the setup into a strict circular sequence:

  • All 41 men stand in a numbered circle.
  • Instead of killing the person directly next to them, they skip a fixed number of people. In the classic mathematical variant, they go around the circle and execute every 3rd living person.
  • For example, numbering the people from 1: Person #3 is killed first, then #6, then #9. Once the count goes all the way around, it skips over the men already killed and continues counting only the surviving men.
  • You can work out mathematically which starting positions are eliminated last. For a circle of 41 people where every 3rd person is eliminated, the positions that survive to the end are 16 and 31.

We will take a computational approach to the Josephus Problem. We simulate the elimination and find the winner that way, instead of calculating it mathematically.

So let’s trace a small example: n = 6 and k = 3. The circle starts as 0, 1, 2, 3, 4, 5.

  • We start counting at person 0. Since k is 3, we count 0, 1, 2 and eliminate person 2. The count resumes at person 3.
  • Count 3, 4, 5: person 5 is eliminated. The count resumes at person 0.
  • Count 0, 1, 3: person 3 is eliminated. (We skipped over 2 because they were eliminated already.) The count resumes at person 4.
  • Count 4, 0, 1: person 1 is eliminated. (We skipped over 5 because they were eliminated already.) At this point, people 2 and 3 are already eliminated, so the count resumes at person 4.
  • Count 4, 0, 4: person 4 is eliminated. (Only persons 0 and 4 remain, so the count lands on person 4 twice.) Only person 0 remains.

The winner is person 0.

The signature of the method in Java might look like this:

public static int survivor(int n, int k) {
  // Your implementation goes here
}

I called the method survivor because it finds the one person left at the end, the winner of the Josephus Problem.

The problem has a constraint: solve it in time.

Let’s think of some special or edge cases as well:

  • If n is 1, there is no one else to eliminate, and person 0 survives no matter what k is.
  • If k is 1, every count lands on the next person in the circle: 0 is eliminated first, then 1, then 2, and so on. The survivor is person n - 1.
  • k can be larger than n. The count then goes around the circle more than once before someone is eliminated, but nothing about the rules changes.