Josephus problem

Josephus problem statement can be found here.

We will try to solve this problem using dynamic programming. Other choice is to use queues or circular buffers to hold the participants.

Let’s try an example with N participants = 5 and k-th execution = 3.

0>1>2>3>4>0…. 5 participants; we start from 0, 3rd is 2, which is removed

0>1>3>4>0… 4 participants; we start from 3, 3rd is 0, which is removed

1>3>4>1… 3 participants; we start from 1, 3rd is 4 which is removed

1>3>1… 2 participants; we start from  1, 3rd is 1 which is removed.

The winner is 3. Hooray.

After each step, the problem has 1 less participant; also, all participants are shifted by k positions. All is wrapped over the current number of participants in the circle.

We can deduce a formula f(n,k) which offers us the position of the participant that is spared given n participants and k-th execution.

f(n,k)=(f(n-1,k)+k) mod n

The base case: f(1,k) = 0.

The actual implementation of the above formula is easy.

static int josephus(int n, int k)
{
    if (n == 1)
        return 0;
    else
        return (josephus(n - 1, k) + k) % n;
}
Advertisements