Find the Winner of the Circular Game

Start dumb: act it out

The problem is a procedure, so the honest first solution is to perform it: put 1..n in a list, keep an index, and each round step forward k positions over whoever is left, delete that friend, and continue from the next one. Repeat until a single friend remains. That’s exactly the code the player runs — clear, correct, and O(n·k) because each of the n−1 deletions walks up to k steps (and a list removeAt shifts elements).

Find the bottleneck

Walking k positions and shifting a list on every elimination is a lot of work for a question that only wants one number: the survivor’s seat. The whole circle is being maintained just to read off a single final index.

The optimal shape

Two ways to land the answer:

1. Simulate (shown here): a list, an index, (start + k − 1) % size, delete, repeat. Easiest to see; every elimination is a real, visible move.
2. Recurrence: fold f(n) = (f(n-1) + k) mod n from f(1) = 0 up to n, then return f(n) + 1 to convert the 0-based seat to a 1-based friend number.

Both give the same winner; the recurrence just refuses to move any friends around. In the player, the count starts at the start pointer and lands on out — the friend who leaves. Eliminated friends stay in place on dashed tiles so you can watch the count skip over them.

Watch it think

Run the default 5 | 2 (winner 3), then 6 | 5 (winner 1 — a larger step that wraps the circle), and 1 | 1, where the game is over before it starts.

1fun findTheWinner(n: Int, k: Int): Int {
2    val circle = (1..n).toMutableList()
3    var start = 0
4    while (circle.size > 1) {
5        val idx = (start + k - 1) % circle.size
6        circle.removeAt(idx)
7        start = idx
8    }
9    return circle[0]
10}