Created
March 22, 2017 15:30
-
-
Save M-ZubairAhmed/98f56cca11602f4d0d50104c37d83b17 to your computer and use it in GitHub Desktop.
This algorithm calculates safe position when Josephus circle game is played
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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