What is Josephus Problem and how to solve it without any in-built function?

This article contains information about what is Josephus Problem and to solve it from scratch means, without using any in-built function in C++ language.

What is Josephus Problem?

The problem is named after Flavius Josephus, a Jewish historian. According to Josephus, he and his 40 soldiers were trapped in a cave by Roman soldiers. They chose suicide over capture, and settled on a serial method of committing suicide by drawing lots. Josephus states that, by luck or possibly by the hand of God, he and another man remained until the end and surrendered to the Romans rather than killing themselves.

In computer science, Josephus problem is a theoretical problem in which “n” people standing in a circle waiting to be executed. The counting out begins at some point in a circle and proceeds around the circle in a fixed direction.
In each step, certain number of people are skipped and next person is killed, until only last one person remains, who is given freedom.

Note ::
i} Numbering represents person.
ii} Objective is to check the last man standing.
iii} Follow circle from start point.
iv} New counting begins from the person who gets killed.

Let’s understand this problem with an example,
Suppose,
Input ::
n=4; where n is no. of people
k=3; where k is which person to kill (i.e. skip first 2, kill third one and so on.)
Output ::
Last man standing → 1
Explanation ::

• Add all values from 1 to n in a list/array.

• Now, 3 will be killed (as k=3) and removed from list. New counting begins from 4 itself.

• Now, 2 will be killed (as k=3) and removed from list. New counting begins from 4 itself.

• Now, 4 will be killed (as k=3) and removed from list.

• Last man Standing would be ::

Approach to solve this problem without any in-built function

This problem can be solved in multiple ways like using array or recursion as well. I am gonna solve it using Singly Circular Linked List in C++ Language. Steps ::

I} Create a node class where, each node represents a person.
II} Create a class for singly circular linked list, which creates and solves Josephus problem.
III} Maintain start point or head node and keep linking last node to head node for next counting.
IV} Display the last man standing.

Source Code → Click here

Conclusion

Josephus problem is a well known problem and easy way to understand is by using Singly Circular Linked List.

Keep Learning
Keep Coding
Thank YOU…!!!