Josephus problem and recursive solution in Java

In this tutorial, we will be learning Josephus problem and its recursive solution in Java.

Suppose we have p persons standing in a circle. In the beginning, there is a sword in someone’s hand, and the game proceeds in a particular direction (clockwise or anticlockwise). He has to skip a few alive people and kill someone. The next alive person of the killed one will be given the sword in the next turn. The game will proceed in the same manner. The game will be stopped when only one person is left. Our task is to find the safe position to survive till the last.

Suppose we have p persons in the circle and a factor s. Initially, the first positioned person is holding the sword. We have to skip (s-1) alive persons (including the person holding the sword) and kill the s-th person. When we kill a person, immediately the next alive person is given the sword. This process continues until only one person is alive. Let’s try to understand with an example.

Suppose we have p as 4 and s as 2. In the first turn, 1 kills 2, and 3 gets the sword. Then, 3 kills 4, and 1 gets the sword. Next, 1 kills 3, and 1 gets the sword. Now only one person is alive i.e. 1. So, the safe position for this case is 1.

Josephus Problem (Recursive approach) in Java

Approach:

When the first person is killed, there are (p-1) persons left. So, we will recursively call for Josephus(p-1, s). The value returned by Josephus(p-1, s) is considering the starting position as s%p + 1. So, we have to adjust the position returned by Josephus(p-1, s). That’s how the problem can be solved easily using recursion.

  Pseudo Code:
    
    Josephus(p, s) = (Josephus(p-1, s) + s-1)%p + 1    // if p is not 1.
    Josephus(1, s) = 1

Drawback:

This solution, using recursion, is easy to understand but there is a drawback too. This approach is not helpful for large inputs as stack overflow will occur.

Code:

public class Solution {

    // Function to find safe position.
    static int Josephus(int p, int s) {

        // Base case.
        if(p == 1)
            return 1;

        // Recursion call and adjusting the position.
        return (Josephus(p-1, s) + s-1)%p + 1;
    }

    // Driver main function.
    public static void main(String[] args) {

        int p = 4, s = 2;

        int rel = Josephus(p, s);

        System.out.println("Safe Position : " + rel);
    }
}

Output:

    Safe Position : 1

Time Complexity:

We will have p recursion calls, where p is the number of people. So, the overall time complexity becomes O(p).

 

Related article:

Solve Coin Change problem in Java