The first-century historian, Flavius Josephus, recounts the story of how, when his band of 41 soldiers was

Question:

The first-century historian, Flavius Josephus, recounts the story of how, when his band of 41 soldiers was trapped by the opposing Roman army, they chose group suicide over surrender. They collected themselves into a circle and repeatedly put to death every third man around the circle, closing up the circle after every death. This process repeated around the circle until the only ones left were Josephus and one other man, at which point they took a new vote of their group and decided to surrender after all. Based on this story, the Josephus problem involves considering the numbers 1 to n arranged in a circle and repeatedly removing every mth number around the circle, outputting the resulting sequence of numbers. For example, with n = 10 and m = 4, the sequence would be 

4, 8, 2, 7, 3, 10, 9, 1, 6, 5. 

Given values for n and m, describe an algorithm for outputting the sequence resulting from this instance of the Josephus problem in O(n log n) time.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Algorithm Design And Applications

ISBN: 9781118335918

1st Edition

Authors: Michael T. Goodrich, Roberto Tamassia

Question Posted: