Back to Solutions

Josephus Problem

Explanation

Here, there are n children in a circle and we need to remove children alternatively. The first child is left and the 2nd is remove, 3rd is left and so on...

This can be done using a set. We can add all the children in the set and then remove the children alternatively.

Code

n = int(input())

numbers = set(range(n))
ans = []
alt = False

while len(numbers) > 1:
    to_remove = []
    for num in numbers:
        alt = not alt
        if not alt:
            ans.append(num + 1)
            to_remove.append(num)
    for num in to_remove:
        numbers.remove(num)

print(*ans, numbers.pop() + 1)