Skip to content

Instantly share code, notes, and snippets.

@M-ZubairAhmed
Created March 22, 2017 15:30
Show Gist options
  • Save M-ZubairAhmed/98f56cca11602f4d0d50104c37d83b17 to your computer and use it in GitHub Desktop.
Save M-ZubairAhmed/98f56cca11602f4d0d50104c37d83b17 to your computer and use it in GitHub Desktop.
This algorithm calculates safe position when Josephus circle game is played
import java.util.ArrayList;
public class JosephusPosition {
public static int josephusSurvivorPosition(final int n, final int k) {
// 'n' is the number of people in the cave of death, such that :- the first person is 1 and last is n
ArrayList soldiers = new ArrayList<>();
for (int j = 1; j <= n; j++) {
soldiers.add(j);
}
int cursor = 0;
while (soldiers.size() > 1) {
cursor = (cursor + k - 1) % soldiers.size();
soldiers.remove(cursor);
}
String josephusPosition = soldiers.toString().replaceAll("\\D", "");
return Integer.valueOf(josephusPosition);
}
}
@M-ZubairAhmed
Copy link
Author

M-ZubairAhmed commented Mar 22, 2017

Josephus problem

People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed.
Wolfram Explanation

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment