Josephus Problem

Problem

Given n people arranged in a circle and a step k, return the 1-based position of the survivor when every k-th person is eliminated repeatedly.

The recurrence P(1) = 0 and P(n) = (P(n-1) + k) mod n gives a 0-based survivor, so add 1 at the end. Assume n >= 1 and k >= 1.

Hint

Solving for n people reuses the answer for n - 1 people shifted by k positions.

case 1

in: [5,2]

expected: 3

case 2

in: [7,3]

expected: 4

case 3

in: [1,1]

expected: 1

case 4

in: [6,5]

expected: 1

case 5

in: [41,3]

expected: 31

Starter codePython

def josephus(n, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor