Josephus Problem

The Josephus Problem, also known as the Josephus Permutation, is a theoretical problem in mathematics and computer science. It generalizes a famous tale of Josephus, a historian, who was among a group of people surrounded and captured by enemies. To avoid capture, the group formed a circle, and every k-th person would step out of the circle and get eliminated. Josephus wanted to be in a position where he wouldn’t be eliminated, so he needed to figure out where to sit. The problem aims to find the position in which to sit to avoid elimination.

Suppose that n people form a circle and that we are given a positive integer m <= n. Beginning with a designated first person, we proceed around the circle, removing every mth person. After each person is removed, counting continues around the circle that remains. This process continues until we have removed all n people. The order in which the people are removed from the circle defines the (n, m) Josephus permutation of the integers 1, 2, … n. For example, the (7, 3) - Josephus permutation is {3, 6, 2, 7, 5, 1, 4}.

In the Josephus problem with 7 people and a step size of 3, you would start counting people in a circle. Every time you get to the third person, that person is removed. In this example, the order people get removed is {3, 6, 2, 7, 5, 1}. The last person left is number 4. So, if you were Josephus and you wanted to be the last person remaining, you would sit in the 4th position.

Java Code for Josephus Problem

Here’s how to solve the Josephus problem in Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public class Josephus {
    public static int josephus(int n, int k) {
        if (n == 1)
            return 0;
        else
            return (josephus(n - 1, k) + k) % n;
    }

    public static void main(String[] args) {
        int n = 7; // Total people
        int k = 3; // Step size
        int safePosition = josephus(n, k) + 1;
        System.out.println("The safe position is " + safePosition);
    }
}

C++ Code for Josephus Problem

Here’s the C++ code snippet:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <iostream>

int josephus(int n, int k) {
    if (n == 1)
        return 0;
    else
        return (josephus(n - 1, k) + k) % n;
}

int main() {
    int n = 7; // Total people
    int k = 3; // Step size
    int safePosition = josephus(n, k) + 1;
    std::cout << "The safe position is " << safePosition << std::endl;
}

Python Code for Josephus Problem

Here’s the Python code snippet:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def josephus(n, k):
    if n == 1:
        return 0
    else:
        return (josephus(n - 1, k) + k) % n

# Example usage
n = 7  # Total people
k = 3  # Step size
safe_position = josephus(n, k) + 1
print(f"The safe position is {safe_position}")

Each implementation uses a recursive function to solve the problem. The function josephus calculates the safe position for n people when every k-th person is eliminated until only one person remains. The safe position is returned, and it’s 1-indexed for ease of understanding.