Josephus problem | iCode

Today we are going to talk about the josephus problem and a codechef problem which is a variant of it.
Josephus problem:
It is the problem in which n people sits on a table and there is elimination of the kth next element. Like for example
Eg.
if n = 5 and k = 2
intially ,
1 2 3 4 5
1 3 4 5
1 3 5
3 5
3.

So three is the answer i.e. given a pair of n and k you have to output the last remaining element.

Solution
There is a very simple Dynamic Programming solution exists for the problem.
Let f(n,k) is the solution for the pair(n,k) ,then

f(n,k) = (f(n-1,k) + k) % n
Base case : f(1,k) =0

We have added k%n to the solution of the pair(n-1,k) because when we eliminate the kth element the (k + 1)th index is treated as 0th index for the f(n-1,k), so as to get the correct answer we have to shift the indices by k%n.

A variant of the problem:

A variant of the problem was asked in codechef recently, You should open the problem and read it first.So as you have read the problem , you might have understood that the above recursion will not work in this case, so we have to modify out recursion as follows:

f(n,k,m) = (f(n-1,k,m+1) + m*k) %n
Base case : f(1,k,m) =0

Read full article from Josephus problem | iCode