Josephus killing problem

#1

please explain the intuition behind josephus killing problem and how it can be solved through recursion?

#2

Let the definition of the function be solve(int n,int k) // n people and k positions
so.solve returns the position of the last person who will survive.

so you have to calculate solve(n,k),
now solve(n,k) = (solve(n-1,k)+k)%n
i.e a person gets killed, last position will be the position : (solve(n-1,k) + k)%n
and base case will be solve(1,k) which is 0. //only one person so position zero.

#3

also please explain the log n approach when k=2

#4

In the case of even n we get that all even numbers will be crossed out, and then there will be a problem remaining for n/2, then the answer for n will be obtained from the answer for n/2 by multiplying by two and subtracting one (by shifting positions):
solve(2n,2) = 2*(solve(n,2))āˆ’1

Similarly, in the case of an odd n, all even numbers will be crossed out, then the first number, and the problem for (nāˆ’1)/2 will remain, and taking into account the shift of positions, we obtain the second formula:

solve(2n+1,2) = 2*solve(n,2)+1