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?

Reproduction

In this version of the Josephus problem, are people zero-indexed? Also, by "step size of k," do you mean that person 0 eliminates person k, or that person 0 is eliminated by person k? – Jeffryjeffy

No, people start from position 1 to n. kth person gets eliminated. So for n=3, and k=2 , 3 is the final answer. – Reproduction

Where did this code come from? – Jeffryjeffy

This is the general code I found at many places. Here is one such place: geeksforgeeks.org/josephus-problem-set-1-a-on-solution – Reproduction

use zero-indexed counting, will simply the recursion formula. if (n==0), return 0; else { return josephus(n-1, k) + k) % n; the insight behind zero-indexed and one-indexed counting are the same, but the process is much easier – Ita

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!

Jeffryjeffy

1. calling josephus(5, 2) will tell you the index of the person out of a ring of five that ends up surviving. 2. The sequence we end up with: 3 4 5 ... n 1 These 2 lines completely removed all my confusions and I see how the optimal substructure property is getting followed. – Reproduction

Also, writing the formula as: k+1 + (josephus(n-1,k)-1) helps understand the problem much better. Great great answer!!! Internet wins again. – Reproduction

Just brilliant, I was searching for an explanation for this problem, and this explains it beautifully. +1. – Contreras

Hi, thanks a lot for this detailed explanation. I've been trying to figure this out all day and this has been the most helpful. But forgive me for being slow, I feel like I'm just a couple of key points away from finally understanding it. From your answer, I understand that josephus(n - 1, k) is the index value of the ultimate survivor in a line of n-1, but why josephus(n , k) can be calculated by (k+1 + josephus(n - 1, k) - 1) % n? The starting point of k+1 is for the line of n-1 but we are calculating the line of n. – Thundersquall

And I am a little confounded by your sentence: So we compute josephus(n - 1, k) to get the one-indexed survivor of a ring of k people, then shift forward by that many steps. First, do you mean a ring of n-1 people? josephus(n - 1, k) is the 1-indexed survivor index value, somehow I feel like (k+1 + josephus(n - 1, k) - 1) % n is giving me the index position of the ultimate survivor in a line of n-1 had it not been for the %n part. Thanks. – Thundersquall

Still not clear about these lines "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" – Humfrey

@Humfrey To get to position k in a 1-indexed array, you begin at position 1, then walk forward k-1 positions. For example, to get to position 3 in a 1-indexed array, you start at position 1 and then take 3-1 = 2 steps forward. – Jeffryjeffy

Answer 2

We need to adjust the position by k-1 simply because the starting position has been shift by k after the kth is removed (and the first k-1 are rotated to the end). That is, initial position pos becomes pos-k. If k = 3, (n-1,k) returned pos = 2, the original position should be pos + k = 5.

We replace k with k-1 in the formula because we have to mod(n): k = (k-1) % n + 1

Cepeda

Welcome to Stack Overflow! Please take a moment to read through the editing help in the help center. Formatting on Stack Overflow is different than other sites. – Carbolize

Hello, can you please tell me, why (f(k-1,n)+k)%n is not working?, But when I do it manually I am getting the same answer. ex: n=5, k=3 1 2 3 4 5 +3 ------------- 4 5 6 7 8 %5 ----------- 4 5 1 2 3 It is giving same output as (f(k-1, n)+k-1)%n+1 – Teleology

Answer 3

we have to find josephus(n,k),an example [1 2 3 4 5 6 7 8,9],here n=9, now let's assume this array[0 1 2 3 4 5 6 7 8],at last in answer we add 1 than ultimately no change,
k=3,start_idx=0; and then we have to remove 2,now array is like
[0 1 3 4 5 6 7 8],now answer is in this array A=[3 4 5 6 7 8 0 1] because the
starting is now from 4th index
k=3,start_idx=0,
if we find answer of the array B=[0 1 2 3 4 5 6 7] and add in this answer k and modulo with n+1 respectively ,than we can find the real answer,

proof. array A = (array B + k)%n+1; than answer also the element of these array, than now our aim is to find josephus(n-1,k) and add in this answer k and modulo with n+1 respectively, now recursive continuous recursive calls we can find a array of size 1 that our answer is zero , and as i discuss in starting about adding one in last,

EX-> assume array [1 2 3 4 5 6 7 8 9] and n=9 and k=3;
let's assume it [0 1 2 3 4 5 6 7 8] ,final_ answer = answer+1;
now as k=3, than our after removal of 2 array is [0 1 3 4 5 6 7 8] now our aim to find answer in [3 4 5 6 7 8 0 1] array,
B = [3 4 5 6 7 8 0 1] == A = [0 1 2 3 4 5 6 7],if we find answer in array A and add in this (answer of array A + k)%n than that is our actual answer, and now recursive calls find answer of this.

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

Hsinking