Find the Winner of the Circular Game — Editorial

Opening the reading…

Intuitionwhy the circle can be rebuilt from one friend

The game is easy to simulate directly: keep the remaining friends, count k positions, remove that friend, and continue from the next position. However, removing from a list also changes the positions of every friend after the removal, so a direct simulation spends extra work maintaining the circle.

Instead, solve smaller circles first. In a circle containing one friend, the winner has zero-based position 0. Suppose you already know the winner's position in a circle of i - 1 friends. When one new friend is added, the elimination process in the larger circle shifts every relevant position by k, so the old winner's new position is (old position + k) % i. Repeating this from i = 2 through n leaves the winner's position in the original circle.

The recurrence uses zero-based positions because modular arithmetic naturally produces values from 0 through i - 1. The friends in the statement are numbered from 1, so add 1 only once at the end.

Approachbuild the answer for circles of increasing size

Set winner to 0, the only valid zero-based position when the circle contains one friend; starting from another value would give the recurrence the wrong base case.

For every circle size i from 2 through n, update winner to (winner + k) % i; the modulo keeps the translated position inside the current circle.

Interpret winner as the winner's zero-based position in the circle of size i, not as a friend number; mixing these meanings introduces an off-by-one error into every update.

After the loop, return winner + 1 because the original friends are numbered from 1 to n while the recurrence used positions from 0 to n - 1.

Complexitythe recurrence removes the list entirely

MEASURE	BOUND	WHY
Time	O(n)	The loop performs one constant-time modular update for each circle size from 2 through n, so it executes n - 1 updates and does not revisit any earlier simulation state.
Space	O(1) extra	Only the current winner position and the loop variable are stored. The returned value is a single integer, so there is no output storage to exclude; the bound stays constant even for the largest allowed circle.

n is the number of friends.

Annotated solutionC++ · iterative recurrence · zero-based positions

CPPBuild the zero-based winner for each circle size, then convert it to the required one-based number.

#include <vector>

using namespace std;

class Solution {
public:
    int findTheWinner(int n, int k) {
        int winner = 0;

        for (int i = 2; i <= n; ++i) {
            winner = (winner + k) % i;
        }

        return winner + 1;
    }
};

The line winner = (winner + k) % i is the entire recurrence. The previous winner is measured from the smaller circle's starting point; adding k translates that position to the starting point used by the larger circle, and modulo i wraps it around the new circle. The final +1 belongs outside the loop because only the returned friend number is one-based.

The direct simulation alternativewhen seeing the removals matters more than constant space

CPPMaintain the remaining friend numbers explicitly and erase the counted friend each round.

#include <vector>

using namespace std;

class Solution {
public:
    int findTheWinner(int n, int k) {
        vector<int> friends;
        for (int friendNumber = 1; friendNumber <= n; ++friendNumber) {
            friends.push_back(friendNumber);
        }

        int index = 0;
        while (friends.size() > 1) {
            index = (index + k - 1) % friends.size();
            friends.erase(friends.begin() + index);
        }

        return friends[0];
    }
};

This version follows the statement directly and is often the easiest one to invent under pressure. It is not an optimisation: vector erase shifts later elements, so repeated removals can take O(n^2) time, and the list uses O(n) extra space. The recurrence is preferable when you only need the final winner; simulation is useful when you need to observe or record the elimination order.