Josephus Problem in Java
The Josephus problem is a classic problem of computer science that has been studied for centuries. It is named after Flavius Josephus, a Jewish historian who, according to legend, was trapped in a cave with 40 soldiers during the First Jewish-Roman War. Rather than surrender to the Roman army, the group decided to commit mass suicide, taking turns killing the person next to them until only one person was left. Josephus, however, managed to survive by cleverly positioning himself to be the last person standing.
The Josephus problem is a mathematical puzzle that asks: given a group of n people arranged in a circle, and a number k, which person should be the last to survive when every kth person is killed? The solution to this problem has important applications in computer science, game theory, and cryptography.
One naive approach to solving the Josephus problem is simply simulating the scenario by repeatedly removing the kth person until only one remains. However, this solution has a time complexity of O(n^2), which becomes prohibitively slow for large values of n.
Approach
A more efficient solution to the Josephus problem involves recursively computing the position of the survivor in smaller and smaller circles until we reach a base case of n=1. Specifically, let f(n,k) be the position of the survivor in a circle of size n when every kth person is killed. Then, we can compute f(n,k) recursively as follows:
- If n=1, then f(n,k) = 0 (since the only person left is the survivor).
- If n>1, then f(n,k) = (f(n-1,k) + k) % n, where % denotes the modulo operator.
The above recursive formula works by first finding the position of the survivor in a circle of size n-1 (which is f(n-1,k)), and then shifting this position k steps to the right to account for the kth person being killed. However, since the circle is circular, we need to take the modulo of the resulting position with n to ensure that we wrap around the circle correctly.
To compute the final answer for a circle of size n, we simply call f(n,k) with the appropriate values of n and k. For example, if we have a circle of 10 people and every 3rd person is killed, then the survivor will be in position f(10,3), which can be computed as follows:
f(10,3) = (f(9,3) + 3) % 10
= ((f(8,3) + 3) % 9 + 3) % 10
= (((f(7,3) + 3) % 8 + 3) % 9 + 3) % 10
= (((((f(6,3) + 3) % 7 + 3) % 8 + 3) % 9 + 3) % 10
= (((((3 + 3) % 7 + 3) % 8 + 3) % 9 + 3) % 10
= 4
Thus, the survivor in a circle of 10 people when every 3rd person is killed will be in position 4.
The time complexity of the above solution is O(n), since we only need to compute f(n,k) once for each value of n. This makes it much faster than the naive simulation approach, especially for large values of n.
Josephus.java
import java.util.*;
// Main class declaration
public class Josephus{
public static int josephus(int n, int k) {
// base condition
if (n == 1) {
return 0;
}
return (josephus(n-1, k) + k) % n;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println("Enter number of people in circle");
int n = sc.nextInt(); // number of people in the circle
System.out.println("Enter k i.e., kth person killed");
int k = sc.nextInt(); // every kth person is killed
int survivor = josephus(n, k);
System.out.println("The survivor is in position " + survivor);
}
}
Output:
Enter number of people in circle
10
Enter k i.e., kth person killed
3
The survivor is in position 3
Explanation
This code defines a josephus() method that computes the position of the survivor given the number of people in the circle n and the value of k. It uses the recursive formula described earlier to compute the answer. The main() method simply calls josephus() with the appropriate values and prints the result. You can adjust the values of n and k as needed to test different scenarios.s