In this blog post, I am going to discuss an interesting Josephus problem which you would have studied in the data structure. This problem includes soldiers surrounded by the enemy and only one horse which a single soldier can use to escape out of the enemy. you will also learn how to solve this Josephus problem using a circular linked list.
What is the Josephus problem?
In Joseph problem, few soldiers are surrounded by the enemy and there is only one horse with the soldiers. So only one soldier can escape out of this enemy area or far from the enemy. Now the problem amongst the soldiers is that who will escape using this horse out of all the soldiers.
How the Josephus problem is solved using a circular linked list?
This Josephus problem can easily be solved using a circular linked list. For solving this problem soldiers make a circle and then a random number is picked up using their hat out of many number slips. and in the same manner, the name of a soldier is picked up using a hat by choosing a random paper slip out of many inside the hat.
Now the counting starts at clockwise direction starting from the name of soldiers whose name was picked up and then the count goes on until it reaches the random number n that also was picked up. The soldiers whom this n reaches get removed from this circle.
And the count begins again with the next soldier in the clockwise direction and again the soldier is removed when it reaches the count n. And this process goes on until there is one single soldier left in last and that soldier will get the horse and will escape out of this enemy area.
For understanding the Josephus problem better, we take an example, suppose n = 3 and assume there are five soldiers name as A, B, C, D, and E. Now we start counting three soldiers from A as per the value of n that is 3 so we complete this count at (A, B) C so C will be removed here.
Now again we start counting from D and it again Reaches to (D, E) A so this time A will be eliminated. Now we start counting from B and it reaches (B, D) E and we remove E from the circle. Now again start at B and it reaches again to (B, D) B so this time B will be removed from the list. Thus D is the one who will escape out of this enemy area. See the image for the Josephus problem solution below.
So this is the very natural way to solve this Josephus problem using a circular linked list where each node is treated as a soldier as it was possible to reach any node from any other node by counting around the circle. To represent the removal of a soldier from the circle, a node is deleted from the circular list. Finally, when one node is left ultimately we get the final result or soldier to escape.
Josephus problem is the problems of soldiers who were surrounded by the various enemy with the only horse with them. and now they need to decide whether which soldier will escape using this horse. for solving this problem they make a circle and with the help of a random number and setting a name as a starting point they start counting in a clockwise direction and remove a soldier when they reach the counter. and they repeat this process until one soldier is left and that is the solution to this problem.
In the case of any queries, you can write to us at firstname.lastname@example.org we will get back to you ASAP.
Hope! you would have enjoyed this post about interesting Josephus problem and its solution using a circular linked list.
Please feel free to give your important feedbacks in the comment section below.
Have a great time! Sayonara!