Let us say we have n soldiers standing in a circle. These
soldiers are numbered from 0 to n-1 in a clockwise direction as shown in the
diagram below:
Now there is a cruel king who wants to kill these soldiers. Since he is really cruel, he wants to play a game with the lives of these soldiers. The king moves around in a clockwise circular direction and skips k-1 soldiers and kills the kth soldier. Now, some soldiers are left alive after this, so he again moves in a circle and skips k-1 soldiers and kills the kth soldier. He keeps on doing this process until all the soldiers are killed and only one is remaining. We have to tell who is the lucky soldier to remain alive. (There might be some cases where no soldier remains alive. Think about these cases too!!!).
An example is shown below:
There were 8 soldiers numbered from 0 to 7 and k=3. So, the king starts from the 0th soldier and leaves k-1 i.e. 2 soldiers (0 and 1) and kills the third soldier i.e. the soldier numbered 2 dies. Again, he leaves 2 more soldiers and he kills the soldier numbered 5. Again, he leaves 2 soldiers and the soldier numbered 0 dies. After this, he has completed a circle and 3 soldiers are dead. The circle of remaining soldiers is shown in the image above. Now, he starts from soldier numbered 1 and leaves the soldier numbered 1 and 2 and kills the third soldier i.e the soldier numbered 4. After this, he leaves the next two soldiers and the soldier numbered 1 dies. Now, we are left with only 3 soldiers. So, the king moves in a clockwise direction again, leaves the first two soldiers and kills the third one (numbered 7). Now, we have only two soldiers left. So, the first soldier (numbered 3) is left and the second (numbered 6) is left. So, the king reaches the first soldier back again (numbered 3). He kills this soldier and the soldier numbered 6 remains alive.
So, dear reader, we hope that you have understood the problem completely. If you still have any doubts regarding the question, refer to the JOSEPHUS PROBLEM VIDEO to understand the problem completely. We recommend you try to solve this problem on your own first and then move to the solution.
APPROACH:
Let us try to think of how we can think of this problem as a large problem and how we can break it into smaller problems so that we can apply recursion.
Let us take the same example as we took above. Let us say that we have a total of 8 soldiers and the value of k=3. So, the soldiers are standing in the circle and the king kills the 3rd soldier keeping the first two soldiers alive (for now). So, the soldier numbered 2 dies.
Now if we think, the next soldier that will die will be the soldier numbered 5. Now, have a look at the diagram shown below:
In the above image, we have shown that instead of assuming that there are still n soldiers and the king has already killed one and is now going to kill the other, we can think of the situation in the other way too. What is this other way? We can say that there are now n-1 soldiers and the circle starts from kth soldier.
Now, we will transform our problem. What transformation will we apply? Have a look at the image shown below:
Wait, what have we done here? We request you watch the solution video to understand this part first as it can be a little confusing for you to understand it from the article directly.
See, we had 8 soldiers and the king killed one out of those 8. Now, we are left with only 7 soldiers. So, what we did is that we assumed that our problem is now of smaller size. But, to solve it using recursion, the problem needs to be of the same type i.e. the soldiers should be numbered from 0 to n-1. So, we converted the numbers that we have to the 0 too n-1 numbering. That is what the transformation is.
So, if we place the soldiers as shown in the image below, we have transformed their numbers as shown:
So, 3 was transformed to 0, 4 was transformed to 1 and so on. So, what we will be doing now is that we will have the faith on recursion that it can solve this smaller problem where we have n-1 soldiers and it will give us the soldier which remains alive out of these n-1 soldiers.
So, let us say that we get the answer 3 from our recursion i.e. from these n-1 soldiers, the soldier numbered 3 stays alive. (This is just an assumption). So, if the soldier numbered 3 is alive, we cannot print 3. Why? This is because we have transformed the original numbers to the numbers from 0 to n-1 so that we could apply recursion. So, 3 is definitely not the original number of the soldier. It is just a number that we have got after transformation.
So, we need to get our original number back. We know (from img-6) that 3 is the transformed version of number 6. So, it is actually the number 6 soldier who is alive and not the number 3.
We will now see how we can transform our problem into a smaller problem to be solved by recursion.
The Transformation:
First of all we need to understand one very important thing, we do not need any formula for transforming our problem to the smaller version of the recursive problem, we need a formula to transform the smaller version of the problem back to our given problem.
What do we mean by this? See, we have 8 soldiers out of them, the soldier numbered 2 was killed by the king. The remaining soldiers are as shown in the figure:
So, now what do you think we need to do? We have already discussed that we will now solve our problem for the smaller case i.e. the numbers are from 0 to n-1. So, obviously, we know the numbers the soldiers are going to have and we also know that every time, the soldier will be killed from the kth position only. So, we do not need any formula to transform this question situation to the smaller recursive problem that we want to solve as we already know that n will be reduced to n-1 and the soldier who will die will always be at position k.
We actually need a formula to convert our recursive problem to the actual problem. Have a look at the transformation image once again.
So, 3 is transformed to 0 and 4 to 1 and so on. We need to have a formula to transform 0 back to 3 and 1 back to 4 and so on. If we have a look at the transformation carefully, we will understand that we are adding the values of k to the transformed values to get back the original values. For instance, if we add k=3 to 0, we will get 3 and 0 actually corresponds to 3. Similarly, if we add k=3 to 1, we will get 44 and 1 corresponds to 4 in the original problem. But, the confusion arises when we reach soldier number 5 in the recursive problem. Here, when we add k=3 to it, we should get 8 as the answer, but we get the answer 0.
So, let us try once more. If we look at this carefully, add k to the transformed value and take its modulus by n. So, (5+3)%8 i.e. (transformed value + k)%n=0. So, we get 0 corresponding to the value 5. This means we have got the formula to convert the recursive problem back to our original problem.
Original soldier number= (Transformed soldier number + k) % n
So, dear reader, we hope that you understood this properly. If you have any doubts regarding this, refer to the solution video to understand how we derived the formula and how we came to the conclusion that we came to the conclusion that we need the formula only to convert the recursion numbers to the original numbers and not vice versa.
Now that we are clear about the conversion of the recursion back to our original problem. Let us once see how exactly recursion is the recursion going to solve our problem.
The Recursive Procedure:
Let us take a small test case and dry run the procedure that we will follow. Try to find out which soldier will be alive at the end if there are 5 soldiers and k=3. So, did you get it? The answer is 3
Now, let us keep the soldiers in a different way.
So, we have kept the elements in a linear fashion and we have depicted their starting point and their direction in img-9. (Now we will not mark the circular direction again and again in the diagrams).
So, let us try to solve this problem using recursion now. The king will kill the soldier numbered 2 first as k=3.
Now when the king has killed the soldier, the circle starts from the very next soldier and this is what we have shown in the diagram (img-8). This is why 0 and 1 came at the front as the circle will now start from 3. Now, we will apply our recursion and we will say that we now have n-1 i.e. 4 soldiers in the circle and again the soldier at the kth position will be killed.
Again, we will keep on applying the same procedure, until only one element remains. By this, we will get the soldier which remains alive at the end. We recommend you watch the solution video to understand how recursion will work in the above scenario.
Now that we have understood the above procedure, let us write the code.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int k = scn.nextInt();
System.out.println(solution(n,k));
}
public static int solution(int n, int k){
if(n == 1){
return 0;
}else{
return (solution(n - 1, k) + k) % n;
}
}
}
java;
true";
Dear reader, refer to the solution video to understand the above code completely and clear your doubts about the above code if any. Now that we have written the code as well, let us move to the time and space complexity analysis.
Time and Space Complexity Analysis:
Time Complexity:
The time complexity of the above method is O(n) where n is the number of soldiers in the circle.
Space Complexity:
The space complexity of the above solution is O(h) where h is the height of the recursion stack.
So, dear reader, we hope that you have understood the time and space complexity as well. If you have any doubts regarding the procedure or the code, refer to the complete solution video to understand everything properly and clear all your doubts. With this, we have completed this problem.
Suggestions:
Here are some suggestions from our side that you do not want to miss:
This problem is not that difficult if you think about it. So, the lesson that you should learn from here is that do not fear any problem as it might appear difficult to you but it is not that difficult to solve sometimes and on the other hand, there might be various problems which might appear simple to you but they need not be that simple. So, overconfidence and underconfidence, both are harmful for us.
We used modulus operation in the formula that we derived. Why? This is because we have a circular movement and the values move in circular motion with the help of a modulus operation. We highly recommend you revise the queue data structure here, where we talked about this modulus operation and its circular nature in great detail.
We recommend you watch the complete solution video once. This will give you the proper understanding and the insight of the problem. So, keep practicing and moving forward. Till then, Happy Coding!!!
