Josephus Problem

Josephus Problem

In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game.

There are people standing in a circle waiting to be executed. After the first person is executed, certain number of people are skipped and one person is executed. Then again, people are skipped and a person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.

The task is to choose the place in the initial circle so that you are the last one remaining and so survive.

Lets consider 'n' as the number of people and i execute every 'k'th person. What will be the initial position of the survivor?

There are multiple solutions to this. Lets start with the easy on of using a linked list.

Naive solution

1. Create a circular linked list with 'n' nodes each having info about their position in the list.
2. Start at first element.
3. from current element keep moving to next element until you reach 'k'th element.
4. Remove the 'k'th element from the list.
5. Now 'k + 1'th is current element. Repeat steps 3, 4 and 5 until there is only one element in the list.

Now the space complexity is O(n).

You will walk the list 'k' times to one node delete node. Hence the time complexity is O(nk).

More Efficient Solution

A more efficient solution is to use dynamic programming.

We have the recurrence here

f(n,k) = (f(n-1,k) + k)%n with f(1,k) = 0

How does this recurrence work?

Lets consider that i know the survivor position is 's' for a given number of people 'n' and skip count 'k' where i start counting from position 1.

so if the list is as below

1 2 3.......s.....n-1 n

now i want to find the survivor position for n + 1 elements with same skip 'k'.
So let me introduce one more person 'n + 1' as below.

1 2 3.......s.....n-1 n n+1

If i eliminate the 'n + 1'th person first, then, the next time i start counting 'k' from position '1', which would give me the same result when i had only 'n' persons to count - that's 's'.

But here we are starting at position (n + 1 - k). So if i have to start at position '1' then the result will be (s + k)%n.

Thats how we get the above recurrence.

Hope i am clear in explaining this.
You can also have a look at dicussion on Problem - Kidsgame at TopCoder SRM 315 for different solutions to this problem.