History
Josephus Problem is theoretical game named after flavius Josephus, he was historian, who was trapped along with his 40 soldiers in cave. Instead of surrendering to roman soldiers they choose to commit to suicide by drawing lots. Josephus states, by the grace of god or by luck, they were the only two to remain alive and surrender to roman soldiers.
Problem
There are 'n' number of people standing in a row waiting to be executed and only one remains alive. The problem has two values, one is the number of people and other is the way they are executed.
Example
Input : N = 5, K = 2
Output : 3
Firstly, the Person at position 2 is out,
then position 0 goes out, then position 4
Finally, the Person at position 1 is out.
So the Person at position 3 survives.
Input : 7 4
Output : 2
Solution
Time Complexity: theta(2^n)
Space Complexity: theta(1)
import java.util.Scanner;
import java.util.Arrays;
public class Jos {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int temp = n;
int count = 0;
boolean[] arr = new boolean[n];
Arrays.fill(arr, true);
for (int i = 0; i < temp; i++) {
if (n != 1) {
if (arr[i])
count++;
if (count == k) {
arr[i] = false;
count = 0;
n -= 1;
}
if (i == temp - 1) {
i = -1;
}
} else {
break;
}
}
for (int j = 0; j < arr.length; j++) {
if (arr[j])
System.out.println(j);
}
}
}
Top comments (0)