Find the Winner of the Circular Game

Medium Arrays & Hashing Elimination Recurrence Original on LeetCode

Find the Winner of the Circular Game is a medium arrays & hashing problem solved with the elimination recurrence pattern. The best approach, optimal (elimination recurrence), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (simulate with a queue) up.

Problem

n players sit in a circle, numbered 1 to n clockwise. The game starts at player 1. Count k players clockwise, starting with (and including) the player where the count begins; the player you land on leaves the circle. The next count starts from the player right after the one who just left.

Repeat until only one player remains, and return that player’s number.

Examples

Example 1

Input
n = 4, k = 3
Output
1
Why
Players 3, 2 and 4 are knocked out in that order, so player 1 is the last one standing.

Example 2

Input
n = 7, k = 1
Output
7
Why
With k = 1 the player who starts each count is removed, so players leave in order 1, 2, ..., 6.

Example 3

Input
n = 3, k = 3
Output
2
Why
Player 3 leaves first, then the count 1, 2, 1 removes player 1.

Constraints

  • 1 <= k <= n <= 500

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (simulate with a queue)O(n · k)O(n)
Optimal (elimination recurrence)O(n)O(1)

1Brute force (simulate with a queue)

TimeO(n · k)n - 1 rounds, each rotating up to k - 1 players.
SpaceO(n)The queue holds every player still in the game.

Put players 1..n in a queue. Each round, move the first k - 1 players from the front to the back, then remove the player now at the front. When one player is left, that player wins.

  1. Push 1..n into a queue.
  2. While the queue has more than one player: repeat k - 1 times poll the front and add it to the back.
  3. Poll the front once more; that player is out.
  4. Return the only player left.
class Solution {
    public int findTheWinner(int n, int k) {
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            q.offerLast(i);
        }
        while (q.size() > 1) {
            for (int i = 0; i < k - 1; i++) {
                q.offerLast(q.pollFirst());
            }
            q.pollFirst();
        }
        return q.peekFirst();
    }
}

2Optimal (elimination recurrence)

TimeO(n)One constant-time update per circle size from 2 to n.
SpaceO(1)Only the running winner index is stored.

Number the seats 0..n-1. With one player the winner is seat 0. Once the first player at seat (k - 1) % n leaves, the game restarts from the next seat with n - 1 players, so every seat index of the smaller game is shifted by k. If w is the winner's seat for i - 1 players, the winner for i players is (w + k) % i. Build this up from 1 to n and add 1 to convert to a player number.

  1. w = 0 (the winner when only one player is left).
  2. For i from 2 to n: w = (w + k) % i.
  3. Return w + 1.
class Solution {
    public int findTheWinner(int n, int k) {
        int w = 0;
        for (int i = 2; i <= n; i++) {
            w = (w + k) % i;
        }
        return w + 1;
    }
}

Edge cases to test

  • A single player (n = 1): that player wins immediately
  • k = 1: players leave in order and the last one, n, wins
  • k = n: the count wraps exactly once around the full circle on the first round
  • k larger than the number of players left: the count wraps several times

Hints

Hint 1

Simulating the circle directly works for these limits. Which data structure lets you rotate players from front to back?

Hint 2

After the first removal you are left with the same game on n - 1 players, just relabeled. How do positions shift?

Hint 3

If w is the 0-based winner position for n - 1 players, the winner for n players sits at (w + k) % n.

FAQ

What is the best time complexity for Find the Winner of the Circular Game?

Optimal (elimination recurrence) runs in O(n) time and O(1) extra space. One constant-time update per circle size from 2 to n.

Which pattern does Find the Winner of the Circular Game use?

It is a arrays & hashing problem that uses the elimination recurrence pattern.

Is there a brute force solution for Find the Winner of the Circular Game?

Yes. Brute force (simulate with a queue) takes O(n · k) time and O(n) space. Put players 1..n in a queue.

Which edge cases should I test for Find the Winner of the Circular Game?

A single player (n = 1): that player wins immediately; k = 1: players leave in order and the last one, n, wins; k = n: the count wraps exactly once around the full circle on the first round; k larger than the number of players left: the count wraps several times.