the josephus problem is a famous theoretical problem related to a certain countingout game this module provides functions to solve the josephus problem for numpeople and a stepsize the josephus problem is defined as follows numpeople are standing in a circle starting with a specified person you count around the circle skipping a fixed number of people stepsize the person at which you stop counting is eliminated from the circle the counting continues until only one person remains for more information about the josephus problem refer to https en wikipedia orgwikijosephusproblem solve the josephus problem for numpeople and a stepsize recursively args numpeople a positive integer representing the number of people stepsize a positive integer representing the step size for elimination returns the position of the last person remaining raises valueerror if numpeople or stepsize is not a positive integer examples josephusrecursive7 3 3 josephusrecursive10 2 4 josephusrecursive0 2 traceback most recent call last valueerror numpeople or stepsize is not a positive integer josephusrecursive1 9 2 traceback most recent call last valueerror numpeople or stepsize is not a positive integer josephusrecursive2 2 traceback most recent call last valueerror numpeople or stepsize is not a positive integer josephusrecursive7 0 traceback most recent call last valueerror numpeople or stepsize is not a positive integer josephusrecursive7 2 traceback most recent call last valueerror numpeople or stepsize is not a positive integer josephusrecursive1000 0 01 traceback most recent call last valueerror numpeople or stepsize is not a positive integer josephusrecursivecat dog traceback most recent call last valueerror numpeople or stepsize is not a positive integer find the winner of the josephus problem for numpeople and a stepsize args numpeople int number of people stepsize int step size for elimination returns int the position of the last person remaining 1based index examples findwinner7 3 4 findwinner10 2 5 solve the josephus problem for numpeople and a stepsize iteratively args numpeople int the number of people in the circle stepsize int the number of steps to take before eliminating someone returns int the position of the last person standing examples josephusiterative5 2 3 josephusiterative7 3 4 solve the josephus problem for num_people and a step_size recursively args num_people a positive integer representing the number of people step_size a positive integer representing the step size for elimination returns the position of the last person remaining raises valueerror if num_people or step_size is not a positive integer examples josephus_recursive 7 3 3 josephus_recursive 10 2 4 josephus_recursive 0 2 traceback most recent call last valueerror num_people or step_size is not a positive integer josephus_recursive 1 9 2 traceback most recent call last valueerror num_people or step_size is not a positive integer josephus_recursive 2 2 traceback most recent call last valueerror num_people or step_size is not a positive integer josephus_recursive 7 0 traceback most recent call last valueerror num_people or step_size is not a positive integer josephus_recursive 7 2 traceback most recent call last valueerror num_people or step_size is not a positive integer josephus_recursive 1_000 0 01 traceback most recent call last valueerror num_people or step_size is not a positive integer josephus_recursive cat dog traceback most recent call last valueerror num_people or step_size is not a positive integer find the winner of the josephus problem for num_people and a step_size args num_people int number of people step_size int step size for elimination returns int the position of the last person remaining 1 based index examples find_winner 7 3 4 find_winner 10 2 5 solve the josephus problem for num_people and a step_size iteratively args num_people int the number of people in the circle step_size int the number of steps to take before eliminating someone returns int the position of the last person standing examples josephus_iterative 5 2 3 josephus_iterative 7 3 4
def josephus_recursive(num_people: int, step_size: int) -> int:
    
    if (
        not isinstance(num_people, int)
        or not isinstance(step_size, int)
        or num_people <= 0
        or step_size <= 0
    ):
        raise ValueError("num_people or step_size is not a positive integer.")

    if num_people == 1:
        return 0

    return (josephus_recursive(num_people - 1, step_size) + step_size) % num_people


def find_winner(num_people: int, step_size: int) -> int:
    
    return josephus_recursive(num_people, step_size) + 1


def josephus_iterative(num_people: int, step_size: int) -> int:
    
    circle = list(range(1, num_people + 1))
    current = 0

    while len(circle) > 1:
        current = (current + step_size - 1) % len(circle)
        circle.pop(current)

    return circle[0]


if __name__ == "__main__":
    import doctest

    doctest.testmod()