Josephus Problem

The problem

Imagine that you are in a situation where you and your soldiers are trapped and soon the enemy is going to get you, so you decide that you would rather die than fall to the hands of the enemy. Now you and your soldiers formed a cyrcle and you pick 2 integers D and K. Starting from the Dth spot you count up to K and every time the count reaches K that person standing on the current spot commits suicide. You need to figure out where should you stand so that you will be the last person standing. 

This is a true story which happened in the first century.

Implemetnation

First first of all we need to try the link between the problems A[n][k] and the previous ones. For doing that let's calculate the answer by hand for the first integers. Here is a list of the answers for integers form 1 to 6.

N              K	1	2	3	4	5	6
1	1	1	1	1	1	1
2	2	1	2	1	2	1
3	3	3	2	2	1	1
4	4	1	1	2	2	3
5	5	3	4	1	2	4
6	6	5	1	5	1	4

here we can notice and interesting link

when N is 1 for every K the answer is also 1.

A[I][J]=(A[I-1][J]+j-1)%n+1

Or if we want to turn it into a recursive code here is how it will look like

int rec(int n, int k)

{

       if(n==1)

                 return 1; (because for every K when N is 1 the answer is also 1)

       else

                return  (rec(n-1,k) + k - 1 ) %n +1;

}

Note that the smallest index is 1 not 0.

And here is another non recursive apporach

int ans=0;

for( i=1;i<=n;i++)

      ans=(ans+k)%i;

return ans+1;

There is a task in spoj which requires the knowledge of this problem , you can practice what you learnt there. 

http://www.spoj.com/problems/ANARC08H/

And here is the link for getting the full source code for the task above if you want to.