In this blog post(Josephus problem algorithm), I am going to discuss an interesting Josephus problem that you would have studied in the data structure.
This problem(Josephus problem algorithm) includes soldiers surrounded by the enemy and only one horse that a single soldier can use to escape from the enemy. you will also learn how to solve this Josephus problem using a circular linked list.
What is the Josephus problem?
In Joseph’s problem, few soldiers are surrounded by the enemy and there is only one horse with the soldiers. So only one soldier can escape…
… of this enemy area or far from the enemy. Now the problem among the soldiers is 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. To solve 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 in a 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.
The count begins again with the next soldier in the clockwise direction and again the soldier is removed when it reaches the count n.
This process goes on until there is one single soldier left last and that soldier will get the horse and will escape out of the enemy area.
To understand the Josephus problem better, we take an example, suppose n = 3, and assume there are five soldiers named 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 (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 (B, D) B so this time B will be removed from the list. Thus D is the one who will escape from 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.
You can also go through a few more amazing blog links below related to Data Structure:
What is a strongly connected graph? / How do you know if a graph is strongly connected…
Graph: Types of the graph in data structure…
AVL Tree In Data Structure…
What is a tree in the data structure…
What is compaction in memory management…
What is garbage collection and how does it work…
Dynamic Memory Management…
Josephus problem & Circular linked list…
What is a circular linked list…
What are the linked lists in the data structure and their types…
What is the priority queue with an example…
the difference between stack and queue…
What is meant by backtracking in the data structure…
Conclusion:
Josephus’s problem is the problem of soldiers who were surrounded by various enemies with only horses with them. and now they need to decide which soldier will escape using this horse. To solve 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 a5theorys@gmail.com we will get back to you ASAP.
Hope! you would have enjoyed this post about the interesting Josephus problem and its solution using a circular linked list.
Please feel free to give your important feedback in the comment section below.
Have a great time! Sayonara!
