Josephus Problem

Published on 08 October 2021 (Updated: 29 October 2025)
Josephus Problem

Welcome to the Josephus Problem page! Here, you'll find a description of the project as well as a list of sample programs written in various languages.

This article was written by:

Description

There are n people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k (the step count) which indicates that k-1 persons are skipped and kth person is killed in circle. The task is to find out which person will survive.

Example

In this example, 5 people are placed in a circle (n = 5), and the step count is 2 (k = 2).

      [1]
     /   \
  [5]     [2]
   |       |
  [4]-----[3]

The count starts at person 1, and person 2 is executed:

      [1]
     /   \
  [5]     [2] X
   |       |
  [4]-----[3]

The count now starts at person 3, and person 4 is executed:

      [1]
     /   \
  [5]     [2] X
   |       |
X [4]-----[3]

The count now starts a person 5, and person 1 is executed:

      [1] X
     /   \
  [5]     [2] X
   |       |
X [4]-----[3]

The count now starts at person 3, and person 5 is executed:

      [1] X
     /   \
X [5]     [2] X
   |       |
X [4]-----[3]

At the end, person 3 is the survivor.

Requirements

Create a file called "Josephus problem" using the naming convention appropriate for your language of choice.

Write a sample program which accepts an integer n (total number of people in the circle) and k (k-1 number of people to be skipped to kill next person) and provide the output integer of the last person alive.

Testing

Every project in the Sample Programs repo should be tested. In this section, we specify the set of tests specific to Josephus Problem. In order to keep things simple, we split up the testing as follows:

Josephus Problem Valid Tests

Description Input (n) Input (k) Output
Sample Input 5, 2 "5" "2" "3"
Sample Input 7 3 "7" "3" "4"
Sample Input 41 4 "41" "4" "11"

Josephus Problem Invalid Tests

Description Input
No Input  
Empty Input ""
Invalid Input: Not A Number "a"
Invalid Input: No K "1"

All of these tests should output the following:

Usage: please input the total number of people and number of people to skip.

Articles

There are 21 articles: