Vultr DocsLatest Content

Find the Winner of the Circular Game

Updated on 29 May, 2025
Find the Winner of the Circular Game header image

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

  • C++
  • Java
  • Python
cpp 
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;
    }
};

The problem "Find the Winner of the Circular Game" can be tackled using a concise and efficient approach, demonstrated in the provided C++ code. This method involves using a variant of the Josephus problem solution.

The code performs the following operations:

  1. Define a function winnerCircleGame that takes two integer arguments: participants indicating the number of persons in the circle, and steps, which is the count after which a participant is removed.

  2. Initialize a variable answer to 0. This variable will hold the zero-based position of the winner.

  3. Execute a loop starting from 2 up to the number of participants. During each iteration, update the answer by calculating (answer + steps) % index. This step determines the safe position when there are index participants.

  4. After completing the loop, adjust the output from zero-based to one-based by adding 1 to answer.

  5. Return the final value of answer.

This efficient solution has a time complexity of O(n) and solves the problem of determining the winner's position in a circular game efficiently by simulating the elimination steps.

java 
class Solution {

    public int determineWinner(int totalPlayers, int stepCount) {
        int result = 0;
        for (int current = 2; current <= totalPlayers; current++) {
            result = (result + stepCount) % current;
        }
        // Convert to 1-based index
        return result + 1;
    }
}

In the given Java solution for finding the winner of the circular game, the determineWinner function solves the problem using an iterative approach based on the Josephus problem. Here are the key components of the solution:

  • Function Parameters:

    • totalPlayers: The total number of players in the game.
    • stepCount: The count after which a player is eliminated until one player remains.

  • Methodology:

    • Initialize the result variable to 0, representing the initial position.
    • Iterate from the second player (current = 2) up to the total number of players (totalPlayers).
    • For each iteration, update the result using the formula (result + stepCount) % current. This formula efficiently determines the position of the player who survives the steps.
    • After iterating through all players, convert the result to a 1-based index by adding 1, as positions in the problem are typically 1-based.

  • Return Value:

    • The method returns the 1-based index of the remaining player who is the winner of the game.

This approach leverages the properties of modular arithmetic to solve the problem efficiently without needing to simulate the entire removal process, thereby reducing complexity and enhancing performance. Make sure to provide the actual total number of players and the step count to this function accurately to get the correct result.

python 
class Solution:
    def getWinner(self, players: int, step: int) -> int:
        result = 0
        for index in range(2, players + 1):
            result = (result + step) % index
        # Convert to 1-based index from 0-based index:
        return result + 1

In the solution provided for the circular game where a winner needs to be determined, a Python class named Solution is defined with a method getWinner, which solves the problem using the famous Josephus problem algorithm. This method accepts two parameters, players which is the total number of players in the game, and step which specifies the elimination step count (i.e., every step-th player gets eliminated).

Here's a straightforward breakdown of how the solution works:

  • Initialize a variable result to 0. This will hold the position of the last remaining player in the zero-based index.
  • Loop through a range starting from 2 up till the number of players inclusive. For each iteration:
    • Update the result to (result + step) % index. This step calculates the new position of the player who would be safe in this round of elimination.
  • Convert the final result from a zero-based index to a one-based index by adding 1, which aligns with typical human counting.

The method then returns the position of the final player who is the winner. This return value is the 1-based index of the player who survives all rounds of elimination based on the specified step interval.

Comments

No comments yet.