Explanation for recursive implementation of Josephus problem

Question

EDIT: n is the number of persons. k is the kth person being eliminated. So for k=2, every 2nd person is getting eliminated.

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

The code is as simple as it could be. But somehow I am unable to understand this problem (which is a little embarassing to be honest).

The way I am trying to understand it is,

1. josephus(n,k) gives the final solution for a population of size n and step size k.
2. josephus(n,k) can be calculated if we know the solution for josephus(n-1,k). That is in my opinion "optimal substructure property" of dynamic programming.
3. I get that we need to do a MOD N so that in case number goes past n, it will again start counting from 1. (i.e. ensure that addition behaves like we are counting in a circle). But why did we add this "k-1"?

The main question is if we know the correct solution of josephus(n-1,k), how are we calculating the solution to josephus(n,k). We have effectively added one more person to the population and somehow adding this k-1 value is giving me the correct solution (let's ignore mod for a moment).

Can anyone explain this to me that how is the optimal substructure property holding at each step in the problem?

Answer 1

The key insight that made this solution make sense for me is the following: the result of josephus(n, k) is best not thought of as the number that is the Josephus survivor, but rather as the index of the number that is the Josephus survivor. For example, calling josephus(5, 2) will tell you the index of the person out of a ring of five that ends up surviving.

With that intuition in mind, let's think about how the Josephus problem works by looking at a concrete example. Suppose we want to know josephus(n, 2). You can imagine we have n people lined up like this:

1 2 3 4 5 ... n

The first thing that happens is that person 1 kills person 2, as shown here:

1 X 3 4 5 ... n

Now, we're left with a subproblem of the following form: there are n-1 people remaining, every other person is going to be killed, and the first person who will be doing the stabbing is person 3. In other words, we're left with a ring of people shaped like this:

3 4 5 ... n 1

with k = 2. Now, imagine that we make a recursive call to josephus(n - 1, 2), since we have n - 1 people. This will give back the index of who survives in a line of n - 1 people. Given that we have the index of the person who will survive, and we also know who the starting person is, we can determine which person will be left. Here's how we'll do it.

The starting person in this line is the person who comes right after the person who was last executed. This will be person 3. The 1-indexed position of the survivor in the ring of four people is given by josephus(n - 1, 2). We can therefore walk forward josephus(n - 1, 2) - 1 positions, wrapping around the ring if necessary, to get to our final position. In other words, the survivor is given by position

 (3 + josephus(n - 1, 2) - 1) % n

There's a problem with this above formula, though. If we are indeed using one-indexing, what happens if the final survivor is at position n? In that case, we'd accidentally get back position 0 as our answer, but we really want position n. As a fix to this, we'll use a trick for using mod to wrap around with one-indexing: we'll take the inside quantity (the one-indexed position) and subtract one to get the zero-indexed position. We'll mod that quantity by n to get the zero-indexed position wrapped around. Finally, we'll add back one to get the one-indexed position, wrapped around. That looks like this:

(3 + josephus(n - 1, 2) - 2) % n + 1

The -2 term here therefore comes from two independent -1's: the first -1 is because josephus(n - 1, 2) returns a one-indexed index, so to step forward by the right number of positions we have to take josephus(n - 1, 2) - 1 steps forward. The second -1 comes from the fact that we're using one-indexing rather than zero-indexing.

Let's generalize this to work for arbitrary k, not just k = 2. Suppose we want to know josephus(n, k). In that case, person 1 will stab person k, leaving us with an array like this:

1 2 3 ... k-1 X k+1 ... n

We now essentially need to solve a subproblem where person k+1 comes first:

k+1 k+2 ... n 1 2 ... k-1

So we compute josephus(n - 1, k) to get the one-indexed survivor of a ring of n - 1 people, then shift forward by that many steps:

(k+1 + josephus(n - 1, k) - 1)

We need to worry about the case where we wrap around, so we need to mod by n:

(k+1 + josephus(n - 1, k) - 1) % n

However, we're one-indexed, so we need to use the trick of subtracting 1 from the inside quantity and then adding 1 at the end:

(k+1 + josephus(n - 1, k) - 2) % n + 1

which simplifies to

(k-1 + josephus(n - 1, k)) % n + 1

which is equivalent to

(josephus(n - 1, k) + k-1) % n + 1

as in the solution code.

To summarize: the k-1 term comes from starting at position k+1, adding in josephus(n - 1, k) - 1 to shift forward the appropriate amount, then subtracting one and adding one back in at the end to do the correct wraparound.

Hope this helps!