Josephus Problem

Josephus Problem

Josephus problem can be solved using the power of 2. Given that there are total of 2^n people standing in a circle, the start position is 1 and skip is 1, then person at position 1 would always be the winner.

in other words: if we write n such that n = 2^a + l where l is smaller than 2a, and 2^a is the biggest power of n; then the winner will be (2l + 1).

Theorem: n = 2^a + l, where l < 2a W(n) = 2l + 1

Example:

n = 100
n = 64 + 36  (64 is the biggest power of n, and 36 is the reminder)
w(n) = 2 * 36 + 1 = 73 (answer)