Solving Josephus Problem in Java

The Josephus Problem is a theoretical problem related to a certain elimination game. It is called after the Jewish historian Flavius Josephus, who, as per legend, created this technique to evade capture during a siege.

Problem Statement

• n people are standing in a circle, numbered from 1 to n.
• Starting from a given position, every k-th person is eliminated in the circle.
• This process continues until only one person remains.
• The task is to find the position of the last person who survives.

Example 1:

Input: n = 6, k = 4

Output: 5

Explanation: The persons at positions 4, 1, 5, 2, and 6 are killed in order, and the person at position 3 survives.

Example 2:

Input: n = 10, k = 3

Output: 4

Explanation: The persons at positions 3, 6, 9, 2, 5, 8, 1, 7, and 10 are killed in order, and the person at position 4 survives.

Approach: Using List

The Josephus problem can be solved using a list to simulate the elimination process. People are stored in a list, and in each iteration, the person at the calculated index is removed until only one person remains.

Algorithm

Step 1: Initialize a list of people from 1 to n, where each element represents a person in the circle.

Step 2: Set the starting index to 0, which represents the first person in the circle.

Step 3: Iterate while the list size is greater than 1:

• Calculate the index of the person to be eliminated using the formula:
• index = (index + k - 1) % current list size, where k is the step count.
• Remove the person at the calculated index from the list.

Step 4: Update the list size after each elimination and continue the process until only one person remains.

Step 5: Return the last remaining person from the list, which is the safe position.

Implementation

File Name: JosephusProblemList.java

Output:

 
The safe position is: 3   

Time Complexity: O(n²)

Auxiliary Space Complexity: O(n)

Using Iterative Approach

The iterative approach to solving the Josephus problem calculates the safe position by iteratively updating the position for each number of people in the circle. It avoids recursion and directly computes the result with a single loop, achieving linear time complexity and constant space usage.

Algorithm

1. Initialize the safe position to 0 (0-based index), assuming only one person is left.
2. Iterate from 2 to n (the total number of people):
   
   • Calculate the new safe position using:
   • safePosition = (safePosition + k) % i,
   • where i is the current number of people.
3. Update the safe position after each elimination step based on the step count k.
4. Continue the process until all people are eliminated except one.
5. Convert the safe position to a 1-based index by adding 1 and return it as the result.

Implementation

File Name: JosephusProblemIterative.java

Output:

 
The safe position is: 3   

Time Complexity: O(n) The loop runs from 2 to n, performing constant time operations inside.

Auxiliary Space Complexity: O(1) The algorithm uses only a few integer variables (safePosition, i), requiring constant space.

Josephus Problem in Linear Time and Constant Space

The Josephus Problem in linear time and constant space calculates the safe position iteratively, updating the position with each step using the formula (safePosition + k) % i. This approach eliminates the need for recursion, achieving O(n) time complexity and O(1) auxiliary space.

Algorithm

Step 1: Initialize the safe position to 0, assuming only one person remains (0-based index).

Step 2: Iterate from 2 to n (total number of people in the circle):

• Calculate the new safe position using the formula: safePosition=(safePosition+k)%i

where i is the current size of the circle.

Step 3: Update the safe position after each iteration to account for the eliminated person.

Step 4: Continue until the loop reaches n to find the safe position for all n people.

Step 5: Convert the safe position to a 1-based index by adding 1 and return it as the final result.

Implementation

File Name: JosephusProblemConstantSpace.java

Output:

 
The safe position is: 3   

Time Complexity: O(n)

Auxiliary Space Complexity: O(1)

Josephus Problem Using Recursion

The Josephus Problem using recursion solves the problem by reducing the number of people in the circle one by one, calculating the safe position for n-1 people and adjusting the result based on the elimination step k. The recursive formula is josephus(n - 1, k) + k) % n, which finds the new safe position after each elimination.

Algorithm

Step 1: If only one person (n = 1), return 0 (the safe position is the first person).

Step 2: Call the function josephus(n - 1, k) to find the safe position for n - 1 people.

Step 3: Use the formula (josephus(n - 1, k) + k) % n to adjust the position after one person is eliminated.

Step 4: Return the safe position for n people.

Step 5: Convert the result from 0-based to 1-based index by adding 1 and print the safe position.

Implementation

File Name: JosephusProblemRecursion.java

Output:

 
The safe position is: 3   

Time Complexity: O(n)

Auxiliary Space Complexity: O(n)