Josephus Problem

In this lesson, we investigate how to solve the “Josephus Problem” using the circular linked list data structure.

Introduction

Children often play a counting-out game to randomly select one person from the group by singing a rhyme. The purpose is to select one person, either as a straightforward winner, or as someone who is eliminated.

Josephus problem is related to this concept. In this problem, people are standing in one circle waiting to be executed. Following points list the specifications of Josephus problem:

• The counting out begins at a specified point in a circle and continues around the circle in a fixed direction.

• In each step, a certain number of people are skipped and the next person is executed.

For example, if we have $n$ people, and $k-1$ people are skipped every time, it means that the $k$^th person is executed. Here, $k$ is the step-size.

Let’s discuss “Josephus Problem” through an example in the illustration below: