Application of Queue | Josephus Problem | FCFS Job Scheduling | Data Structure & Algorithm | #cs #it

Josephus Problem

In Josephus problem, "n" people stand in a circle waiting to be executed. The counting starts at some point in the circle and proceeds in a specific direction around the circle.

In each step, a certain number of people are skipped and the next person is executed (or eliminated). The elimination of people makes the circle smaller and smaller. Therefore, if there are "n" number of people and a number "k" which indicates that (k-1) people are skipped and k-th person in the circle is eliminated, then the problem is to choose a position in the initial circle so that the given person becomes the winner. At the last step, only one person remains who is declared the 'winner'.

For example, if there are 5 (n) people and every second (k) person is eliminated, then first the person at position 2 is eliminated followed by the person at position 4 followed by person at position 1 and finally the person at position 5 is eliminated. Therefore, the person at position 3 becomes the winner.

Program for Josephus Problem in C shorturl.at/agMQ3

For more details click here