josephus problem

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

I was unable to understand the underlying recursion in it,can any please explain with an example.thanks in advance:)

2

The iterative example makes it easier to understand.

Ideone iterative code

Consider this Eg : n=5 and k=2.
Start from the 1st person (Let a=1). You need to kill Kth person from ā€˜aā€™. Since ā€˜aā€™ himself is the 1st person you need to kill a+(k-1)th person. ( see line 14 of my iterative code)
Now the next starting position is the person next to this dead fellow. ie. next starting position is (a+k-1) + 1.
But if dead fellow is 5, the next starting pos is 6, which is out of range for n=5. So we take (a+k-1) % (no. of remaining/alive people) + 1.
Hence for the iterative method a=(a+k-1)%i+1 , where ā€˜iā€™ represents the no. of alive people .
So basically, a+k-1 => says who will be killed.
(a+k-1)%i+1 => who will be the next person to start from.
In the final iteration that next person is obviously the winner :slight_smile:
This can recurse as return (f(n,k-1)+k-1)%n+1 where f(1,k) = 1.
And (f(n,k-1)+k)%n works if f(1,k) = 0.
Hope this helps :slight_smile:

1 Like