Find the Winner of the Circular Game

Problem Statement

In the described game, n friends are seated in a circular arrangement, each labeled sequentially from 1 to n. They play a game where the process begins with the first friend and involves counting k places clockwise, including the starting point. The friend at this kth position is then eliminated from the circle, and the next round starts immediately to the clockwise side of the last eliminated friend. This continues until only one friend is left, who is declared the winner. The challenge is to determine who the last remaining friend will be based on the given values of n (total number of friends) and k (the count used to determine which friend is eliminated in each round).

Examples

Example 1

Input:

n = 5, k = 2

Output:

3

Explanation:

Here are the steps of the game:
1) Start at friend 1.
2) Count 2 friends clockwise, which are friends 1 and 2.
3) Friend 2 leaves the circle. Next start is friend 3.
4) Count 2 friends clockwise, which are friends 3 and 4.
5) Friend 4 leaves the circle. Next start is friend 5.
6) Count 2 friends clockwise, which are friends 5 and 1.
7) Friend 1 leaves the circle. Next start is friend 3.
8) Count 2 friends clockwise, which are friends 3 and 5.
9) Friend 5 leaves the circle. Only friend 3 is left, so they are the winner.

Example 2

Input:

n = 6, k = 5

Output:

1

Explanation:

The friends leave in this order: 5, 4, 6, 2, 3. The winner is friend 1.

Constraints

• 1 <= k <= n <= 500

Approach and Intuition

The sequential elimination of friends until only one remains can alternatively be perceived as a problem of preserving state in a cycle. The solution requires us to:

1. Understand the progressive reduction of the circle as friends are removed.
2. Recognize that each elimination essentially resets the starting point for the next round, immediately after the location of the last elimination.
3. Note how the counting wraps around once it reaches the last friend, returning to the first.

Given the constraints of the problem (up to 500 friends), an array-based simulation is feasible. Here's the intuition for two common approaches to solve this problem:

• Simulation Using Array/List:

  • Start by simulating the circle with an list of friends.
  • For each step, increment the current index by k, and use modulo operation to wrap around if the index exceeds the length of the list, to find the friend to remove.
  • Remove the friend and adjust the index to start the next round just after the removed friend's index.

• Mathematical Approach (Josephus Problem):

  • This problem is a variant of a known problem in computer science known as the Josephus Problem, which can also be solved using a recursive mathematical formula.
  • With each friend removed, the problem size reduces, and we deal with a new sub-problem which is similar in nature but smaller in size. For a zero-indexed version, the position J(n, k) of the survivor is given by the recurrence relation: [ J(n, k) = (J(n-1, k) + k) % n ]
  • Starting with the base case J(1, k) = 0, meaning that if there's only one person, they are the survivor.

For both methods, once the entire sequence of eliminations is carried out, whichever friend remains (usually tracked by an index or position) is the winner. The choice of method can depend on the preference for either direct simulation that closely follows the problem description or applying a theoretically optimal mathematical formula that solves the generalized version of the problem efficiently.

Solutions

class Solution {
public:
    int winnerCircleGame(int participants, int steps) {
        int answer = 0;
        for (int index = 2; index <= participants; index++) {
            answer = (answer + steps) % index;
        }
        // Convert zero-based result to one-based
        return answer + 1;
    }
};