Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Find the Winner of the Circular Game

Try it yourself
MediumProblemExternal link

Description

n friends, numbered 1 to n, sit in a circle in order: after friend n comes friend 1 again. They play a counting game:

  1. Start at friend 1.
  2. Count k friends clockwise, including the one you start at. The last friend counted leaves the circle.
  3. If more than one friend is left, start again from the friend just after the one who left, and repeat.

Return the number of the friend who is left at the end.

Examples

Example 1

Input: n = 5, k = 2

Output: 3

Explanation: Counting every 2nd: out go 2, 4, 1 and 5, in that order, and 3 is left.

Example 2

Input: n = 6, k = 5

Output: 1

Explanation: Counting every 5th: out go 5, 4, 6, 2 and 3, and 1 is left.

Example 3

Input: n = 1, k = 1

Output: 1

Explanation: One friend wins without playing.

Constraints

  • 1 ≤ k ≤ n ≤ 500

Editorial

Brute Force

Intuition

Play the game. Put the friends in a queue whose front is the next friend counted. Counting a friend who stays means moving them from the front to the back, the next seat round the circle. So move k - 1 friends to the back, and the friend at the front is the k-th: they leave. Repeat until one is left.

Step-by-Step Explanation

Let's trace n = 5, k = 2:

  1. Count 1, moving it to the back. The 2nd counted is 2, and 2 leaves.
  2. Count 3, moving it to the back. The 2nd counted is 4, and 4 leaves.
  3. Count 5, moving it to the back. The 2nd counted is 1, and 1 leaves.
  4. Count 3, moving it to the back. The 2nd counted is 5, and 5 leaves.

Friend 3 is left.

5 Friends, Every 2nd Leaves — Friends counted but kept go round to the back; the k-th one counted leaves.

Algorithm

  1. Push friends 1 to n into a queue.
  2. While more than one friend is in the queue: k - 1 times, pop the front and push it to the back; then pop the front, who leaves.
  3. Return the friend left in the queue.

Code

JavaScript keeps the queue in an array with a head index instead of calling shift().

class Solution {
public:
    int findTheWinner(int n, int k) {
        queue<int> circle;                   // the front is the friend counted next
        for (int i = 1; i <= n; i++) circle.push(i);
        while (circle.size() > 1) {
            for (int c = 1; c < k; c++) {    // counted but safe: round to the back
                circle.push(circle.front());
                circle.pop();
            }
            circle.pop();                    // the k-th friend counted leaves
        }
        return circle.front();
    }
};

from collections import deque

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        circle = deque(range(1, n + 1))      # the front is the friend counted next
        while len(circle) > 1:
            for _ in range(k - 1):
                circle.append(circle.popleft())   # counted but safe: round to the back
            circle.popleft()                 # the k-th friend counted leaves
        return circle[0]

class Solution {
    public int findTheWinner(int n, int k) {
        Deque<Integer> circle = new ArrayDeque<>();   // the front is the friend counted next
        for (int i = 1; i <= n; i++) circle.offerLast(i);
        while (circle.size() > 1) {
            for (int c = 1; c < k; c++) circle.offerLast(circle.pollFirst());   // counted but safe
            circle.pollFirst();                       // the k-th friend counted leaves
        }
        return circle.peekFirst();
    }
}

var findTheWinner = function(n, k) {
    const circle = [];                       // a queue: circle[head] is the friend counted next
    for (let i = 1; i <= n; i++) circle.push(i);
    let head = 0;
    while (circle.length - head > 1) {
        for (let c = 1; c < k; c++) circle.push(circle[head++]);   // counted but safe: round to the back
        head++;                              // the k-th friend counted leaves
    }
    return circle[head];
};

Complexity Analysis

Time Complexity: O(n·k)

Each of the n − 1 rounds moves k − 1 friends and removes one.

Space Complexity: O(n)

The queue of friends.

Why This Approach Is Not Efficient

At n = k = 500 it's 250,000 moves, which is quick. But every round is played out friend by friend, and the queue holds everyone. The winner can be found without playing at all.

Number the seats from 0, starting where the counting starts. In a circle of size friends, the first to leave sits at seat (k - 1) % size, and counting goes on from seat k % size. What's left is a circle of size - 1 friends that plays the same game from its own seat 0. So if you already know that smaller circle's winning seat w, the same friend sits at seat (w + k) % size in the bigger one. Start from one friend, seat 0, and grow the circle one friend at a time.

Optimal Approach - The Josephus Recurrence

Intuition

Let winner(size) be the winning seat, counted from 0, in a circle of size friends where counting starts at seat 0. With one friend, winner(1) = 0. Each bigger circle is the smaller one shifted by k seats, because the smaller game starts k seats further round:

winner(size) = (winner(size - 1) + k) % size

Apply it for size from 2 to n, keeping only the latest value, and add 1 to turn the seat into the friend's number.

Step-by-Step Explanation

Let's trace n = 5, k = 2:

  1. A circle of 2: winner = (0 + 2) % 2 = 0.
  2. A circle of 3: winner = (0 + 2) % 3 = 2.
  3. A circle of 4: winner = (2 + 2) % 4 = 0.
  4. A circle of 5: winner = (0 + 2) % 5 = 2.

Seat 2 is friend 3, the same answer the queue found.

Grow the Circle, Shift the Winner — The green seat is the winner for each size of circle, counted from 0.

Algorithm

  1. winner = 0.
  2. For size from 2 to n: winner = (winner + k) % size.
  3. Return winner + 1.

Code

class Solution {
public:
    int findTheWinner(int n, int k) {
        int winner = 0;                      // one friend: seat 0 wins (seats are counted from 0)
        for (int size = 2; size <= n; size++)
            winner = (winner + k) % size;    // one more friend shifts every seat by k
        return winner + 1;                   // friends are numbered from 1
    }
};

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        winner = 0                           # one friend: seat 0 wins (seats are counted from 0)
        for size in range(2, n + 1):
            winner = (winner + k) % size     # one more friend shifts every seat by k
        return winner + 1                    # friends are numbered from 1

class Solution {
    public int findTheWinner(int n, int k) {
        int winner = 0;                      // one friend: seat 0 wins (seats are counted from 0)
        for (int size = 2; size <= n; size++)
            winner = (winner + k) % size;    // one more friend shifts every seat by k
        return winner + 1;                   // friends are numbered from 1
    }
}

var findTheWinner = function(n, k) {
    let winner = 0;                          // one friend: seat 0 wins (seats are counted from 0)
    for (let size = 2; size <= n; size++)
        winner = (winner + k) % size;        // one more friend shifts every seat by k
    return winner + 1;                       // friends are numbered from 1
};

Complexity Analysis

Time Complexity: O(n)

One step per size of circle.

Space Complexity: O(1)

One number.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Returning the seat instead of the friend. return winner

On n = 5, k = 2 it returns 2; the answer is 3. The recurrence numbers the seats from 0, so the last seat left is one less than the friend's number. Add 1 at the end.

Restarting the count at friend 1. friends.pop((k - 1) % len(friends))

On n = 5, k = 2 it returns 1; the answer is 3. After a friend leaves, counting goes on from the next friend in the circle, not from the start of the list. Restarting at the first seat every round removes the wrong friends.

Counting the friend who just left. at = (at + k) % len(friends)

On n = 6, k = 5 it returns 3; the answer is 1. When the friend at seat at leaves, the next friend slides into seat at, and that friend is the first one counted next. Moving on by k from there counts k + 1 friends; move on by k − 1.

Where This Pattern Is Taught

This problem practises running a process with a queue. It's taught in Introduction to Queues, where the Josephus circle is one of the three simulations a queue runs, and the lesson points to this formula for a huge n.