25

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?

5
  • 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? Aug 2, 2015 at 19:37
  • No, people start from position 1 to n. kth person gets eliminated. So for n=3, and k=2 , 3 is the final answer.
    – rents
    Aug 2, 2015 at 19:38
  • Where did this code come from? Aug 2, 2015 at 19:51
  • This is the general code I found at many places. Here is one such place: geeksforgeeks.org/josephus-problem-set-1-a-on-solution
    – rents
    Aug 2, 2015 at 20:05
  • 1
    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 Sep 10, 2020 at 13:50

2 Answers 2

37

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!

7
  • 1
    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.
    – rents
    Aug 2, 2015 at 20:41
  • 1
    Also, writing the formula as: k+1 + (josephus(n-1,k)-1) helps understand the problem much better. Great great answer!!! Internet wins again.
    – rents
    Aug 2, 2015 at 20:43
  • Just brilliant, I was searching for an explanation for this problem, and this explains it beautifully. +1. Jun 7, 2019 at 9:37
  • 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.
    – Bowen Liu
    Dec 18, 2019 at 2:06
  • 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.
    – Bowen Liu
    Dec 18, 2019 at 2:18
0

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

2
  • 1
    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.
    – Ghost
    Aug 23, 2021 at 5:13
  • 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
    – NAIDU
    May 24 at 2:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.