I came across the following challenge. Here is my implementation in Python 3.7
A room has 100 chairs numbered from 1-100. On the first round of the game the FIRST individual is eliminated. On the second round, the THIRD individual is eliminated. On every successive round the number of people skipped increases by one (0, 1, 2, 3, 4...). So after the third person, the next person asked to leave is the sixth (skip 2 people - i.e: 4 and 5).
This game continues until only 1 person remains.
Which chair is left by the end?
I actually don't know what the true answer is, but my code outputs
I think this is the fastest solution and at worst has an
O(N^2) time complexity
n = 100 skip = 0 players = [x for x in range (1, n+1)] pointer = 0 while len(players) > 1: pointer += skip while pointer >= len(players): pointer = pointer - len(players) players.pop(pointer) skip += 1 print(players)