Code Implementation

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        res = 0
        for i in range(2, n + 1):
            res = (res + k) % i
        return res + 1
      

class Solution {
public:
    int findTheWinner(int n, int k) {
        int res = 0;
        for (int i = 2; i <= n; ++i) {
            res = (res + k) % i;
        }
        return res + 1;
    }
};
      

class Solution {
    public int findTheWinner(int n, int k) {
        int res = 0;
        for (int i = 2; i <= n; i++) {
            res = (res + k) % i;
        }
        return res + 1;
    }
}
      

var findTheWinner = function(n, k) {
    let res = 0;
    for (let i = 2; i <= n; i++) {
        res = (res + k) % i;
    }
    return res + 1;
};
      

Problem Description

You are given two integers, n and k. There are n friends sitting in a circle, numbered from 1 to n in clockwise order. The game proceeds as follows:

• Starting from the first person, count k people clockwise (including the current person).
• The k-th person is removed from the circle and the count resumes from the next person.
• This process repeats until only one person remains.

Return the number of the person who is the last remaining (the winner).

Constraints:

• 1 ≤ k ≤ n ≤ 500
• There is always exactly one winner.
• Once a person is removed, they cannot re-enter the circle.

Thought Process

At first glance, this problem resembles the classic Josephus problem, where people are eliminated in a circle at fixed intervals. The naive approach would be to simulate the process: maintain a list of people, repeatedly remove every k-th person, and continue until one remains.

However, simulating the entire process can be inefficient for larger n, as removing elements from a list or array repeatedly can be costly. This leads us to consider if there's a mathematical or recursive way to find the winner's position without simulating every step.

The key insight is that the problem has a recursive structure: the winner of n people with step k can be determined from the winner of n-1 people, adjusted for the new circle size. This recursive relationship is the heart of the Josephus problem and enables an efficient solution.

Solution Approach

To solve the problem efficiently, we use the recursive formula for the Josephus problem:

• Let f(n, k) be the zero-based index of the winner in a circle of size n with step size k.
• The base case is f(1, k) = 0 (with only one person, they are the winner).
• For n > 1, f(n, k) = (f(n-1, k) + k) % n.

This formula works by:

1. Solving the problem for n-1 people.
2. Adjusting the position by adding k (the step size), and taking modulo n to wrap around the circle.

To implement this efficiently, we can use an iterative approach, starting with res = 0 for one person and incrementally building up to n, each time updating res as (res + k) % i for i from 2 to n.

Finally, since the problem uses 1-based numbering, we return res + 1 as the winner.

Example Walkthrough

Let's walk through an example with n = 5 and k = 2:

• Initial circle: [1, 2, 3, 4, 5]
• Start at 1, count 2: remove 2. Circle: [1, 3, 4, 5]
• Next is 3, count 2: remove 4. Circle: [1, 3, 5]
• Next is 5, count 2: remove 1. Circle: [3, 5]
• Next is 3, count 2: remove 5. Circle: [3]
• Winner is 3.

Using the iterative formula:

• res = 0 (for n=1)
• n=2: res = (0+2)%2 = 0
• n=3: res = (0+2)%3 = 2
• n=4: res = (2+2)%4 = 0
• n=5: res = (0+2)%5 = 2

Final answer: res + 1 = 2 + 1 = 3 (which matches our manual simulation).

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(n²), since each elimination can take up to O(n) time (removing from a list) and we repeat this n times.
• Space Complexity: O(n), to store the list of people.

• Time Complexity: O(n), since we loop once from 2 to n.
• Space Complexity: O(1), since only a few variables are used; no extra list is needed.

The optimized approach is much more efficient and suitable for large values of n.

Summary

The "Find the Winner of the Circular Game" problem is a variant of the Josephus problem. By recognizing its recursive structure, we can avoid brute-force simulation and instead use a simple iterative formula to compute the winner in O(n) time and O(1) space. The key insight is mapping the problem to its mathematical recurrence, which leads to an elegant and efficient solution.