A queue: first in, first out
Join at the back, leave from the front. About 10 minutes.
Think of the line at a canteen counter. People join at the back and are served from the front. Whoever came first leaves first, which is what makes a queue fair.
A queue has two moves: add at the back, and take from the front. Never the other way round.
from collections import deque
line = deque(players)
while len(line) > 1:
line.append(line.popleft())
line.popleft()
return line[0]1 is at the front and walks to the back. Then 2 is at the front and leaves. Line: [3, 4, 5, 1].
Don't take from the front of a plain list
In Python, removing the first item of a list, in JavaScript shift, and erasing the first item of a C++ vector all make every other item step one place to the left, like a whole queue shuffling forward each time one person leaves.
Use a real queue instead: deque in Python, queue in C++, and ArrayDeque in Java. In JavaScript, keep an array and a head index that marks the front, and move the index forward instead of removing.
What does the line look like after one round?
line = [6, 2, 8], front first. The front walks to the back, then the new front leaves.
- A[8, 6]
- B[2, 8]
- C[6, 8]
Show the answer
[8, 6]. 6 walks to the back: [2, 8, 6]. Then 2 leaves: [8, 6].
Pass and leave
Players stand in a line. players[0] is at the front. Until only one player is left, repeat two moves: the player at the front walks to the back of the line, and then the player now at the front leaves the game. Return the number of the last player left.
players = [1, 2, 3, 4, 5] → 3
1 ≤ n ≤ 1,000,000 · 0 ≤ each number ≤ 2,000,000,000 · the numbers are all different