This is the most famous question from recursion.
This is one of the most famous problems from recursion which is frequently asked in coding competitions or coding interviews.
The problem is, there are a total n numbers of people in a circle. There is a sword in the hand of 1st person (at position 1), and he has to kill a kth person from him, and then pass the sword to the person next to the one who got killed. After doing the same process several times, only one person will be left safe, so we have to find that safe position.
EXPLAINATION:
Let’s take an example, n=5. We have five peoples in a circle at positions, 1, 2, 3, 4, 5. Sword is in 1st person’s hand. Assume k = 2. 1st person will kill 3rd person, then the sword moves in the hand of 4th person, now he will kill 1st person, and the sword moves to 2nd person, then he will kill 5th person, and the sword moves to 2nd person and he will skip 4th person and will kill himself, as he is at the kth position from himself, and the sword moves to 4th person which is the safest position in the circle.
Consider the following images for better visualization:
RECURSIVE APPROACH
We can write the Josephus Function as :
Josephus(n, k) = (Josephus(n — 1, k) + k-1) % n + 1
After the first person (kth from the beginning) is killed, n-1 persons are left. So we call Josephus(n — 1, k) to get the position with n-1 persons. But the position returned by Josephus(n — 1, k) will consider the position starting from k%n + 1. So, we must make adjustments to the position returned by Josephus(n — 1, k).
I will explain the bitwise approach in my next blog. If you like my blog, please give me a clap, share it, and follow me :)
Happy Coding :)
