josephus-problem-feature-image

Josephus problem & Circular linked list?

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.

josephus-problem
Josephus Solution

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.

Conclusion:

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 a5theorys@gmail.com 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!

circular-linked-list

What is a circular linked list?

A list with various numbers of the node containing data and address pointer and the list start and finish at the same first node is known as a circular linked list. this list forms a circle and having a common start and endpoint.

As in the case of the linked list, we have seen that the first node is pointed by an external pointer and in the last node we have a null value in the field of the address.

We should be very careful while traversing the circular linked list as there is a chance to be stuck in an infinite loop if the end node is unable to detect. To avoid this situation we can set an external pointer at the starting node and now used as the stop point or endpoint of the list.

circularlinkkedlist
Circular linked list

As an alternative method, we can make a header node to our first node and can keep a special value in the info field that will not be connected with other info data in the list, or will not have any relation with another data field. And we will halt traversing circular linked list once this header node is reached.

Conclusion:

Circular linked list in data structure is a list that forms a circle shape while traversing the data element using this list. This circular list has a common starting and ending point which is, in general, is the very first node or header node, which may also be filled with some special data to detect it as a header node where we can stop our traversing.

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 a circular linked list.

Please feel free to give your important feedbacks in the comment section below.

Have a great time! Sayonara!