Josephus problem implementation in java

Finding a solution for a problem is always interesting. Here is the interesting problem called  “Josephus”.

What is the Josephus problem?

It is a classic game involves a eliminating a person from a group of people who stands in a circle. First, ‘n’ number of people in a circle. Count from a position. At the end of counting, eliminate the person. Continue the process until the person.

Java implementation of Josephus problem:

It can be done by two ways.

• ·       Recursive function
• ·       Iterative method

Implementation of Josephus problem using recursive function:

•  It creates a class “Josephuspbm” with a main() function. A recursive function is created with two member variables.
• ·       Check this ‘n’ value. If the n is equal to one, then return to 0. Otherwise, call the recursive function.
• ·       Assign two integer variables with value. One is for total number of people and another one is step count.
• ·       Call the recursive function and print the result.

Program:

public class JosephusPbm{

    // A recursive function to find the last person in the circle

    static int josephus(int n, int k) {

        if (n == 1) {

            return 0;  // one person is left

        } else {

            return (josephus(n - 1, k) + k) % n;

        }

    }

    public static void main(String[] args) {

        int n = 9;  // Total number of people

        int sc = 2;  // Step count

        int res = josephus(n, sc) + 1;

        System.out.println("The last person in the circle is: " + res);

    }

}

Compile and execute this program to get the output.

C:\raji\blog>javac JosephusPbm.java

C:\raji\blog>java JosephusPbm

The last person in the circle is: 3

Implementation of Josephus problem using Iterative function:

              Here, instead of a recursive function, it uses a for loop for iteration.

public class JosephusPbm1 {

    // iterative function

    static int josephusIterative(int n, int k) {

        int res = 0;

        for (int i = 1; i <= n; i++) {

            res = (res + k) % i;

        }

        return res;

    }

    public static void main(String[] args) {

        int n = 9;  // Total people

        int k = 2;  // Step count

        int res = josephusIterative(n, k) + 1;

        System.out.println("The last person in the circle is: " + res);

    }

}

The output is given below.

C:\raji\blog>javac JosephusPbm1.java

C:\raji\blog>java JosephusPbm1

The last person in the circle is: 3

This is the way of implementing Josephus problem in java. Enjoy coding!!!