Find the Winner of the Circular Game

Medium

Asked by:

+6

26 views

Topics:

ArraysRecursionDynamic Programming

There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the i^th friend brings you to the (i+1)^th friend for 1 <= i < n, and moving clockwise from the n^th friend brings you to the 1^st friend.

The rules of the game are as follows:

Start at the 1^st friend.
Count the next k friends in the clockwise direction including the friend you started at. The counting wraps around the circle and may count some friends more than once.
The last friend you counted leaves the circle and loses the game.
If there is still more than one friend in the circle, go back to step 2 starting from the friend immediately clockwise of the friend who just lost and repeat.
Else, the last friend in the circle wins the game.

Given the number of friends, n, and an integer k, return the winner of the game.

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

Follow up:

Could you solve this problem in linear time with constant space?

Find the Winner of the Circular Game

Medium

Asked by:

26 views

Topics:

ArraysRecursionDynamic Programming

There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the i^th friend brings you to the (i+1)^th friend for 1 <= i < n, and moving clockwise from the n^th friend brings you to the 1^st friend.

The rules of the game are as follows:

Start at the 1^st friend.
Count the next k friends in the clockwise direction including the friend you started at. The counting wraps around the circle and may count some friends more than once.
The last friend you counted leaves the circle and loses the game.
If there is still more than one friend in the circle, go back to step 2 starting from the friend immediately clockwise of the friend who just lost and repeat.
Else, the last friend in the circle wins the game.

Given the number of friends, n, and an integer k, return the winner of the game.

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

Follow up:

Could you solve this problem in linear time with constant space?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on n and k? What is the maximum possible value for each?
Is n always greater than 0, and is k always greater than 0?
Does the elimination start at player 1, or is there a possibility it starts at another player?
Could you provide a simple example with n=5 and k=2 to illustrate the elimination process step by step?
Is there a specific return value I should return if n is 0 or 1?

Brute Force Solution

Approach

The brute force approach simulates the game exactly as described. We start with all the players and eliminate them one by one according to the rules until only one player remains. That last player is declared the winner.

Here's how the algorithm would work step-by-step:

Begin with all the players standing in a circle.
Start counting from the first player.
Skip a certain number of players as specified by the rules.
Eliminate the player you land on after skipping the correct number.
Continue counting from the player after the one you just eliminated.
Keep skipping and eliminating players until only one player is left.
The last player remaining is the winner.

Code Implementation

def find_the_winner_circular_game_brute_force(number_of_players, skip_value):
    players = list(range(1, number_of_players + 1))
    current_index = 0

    while len(players) > 1:
        # Adjust the index by the skip value and account for circularity
        current_index = (current_index + skip_value - 1) % len(players)

        # Eliminate the player at the calculated index
        players.pop(current_index)

        # The next player after the eliminated player becomes the new current player
        # This is automatically handled because of the pop operation

    # Return the last remaining player
    return players[0]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach simulates the game step by step. In the worst case, we iterate through the list of players multiple times. For each elimination, we may need to traverse the (shrinking) list of players to find the next player to eliminate. Since we eliminate n-1 players, and in the worst case each elimination requires traversing almost the entire list, the overall time complexity is approximately proportional to (n-1) + (n-2) + ... + 1. This summation simplifies to n(n-1)/2, which is O(n²).

Space Complexity

O(N) – The brute force approach, as described, simulates the game by maintaining a data structure to represent the circle of players. This likely involves using a list or array to keep track of the players who are still in the game. In the worst case, we need to store information about all N players initially. Therefore, the auxiliary space required is proportional to the number of players, N.

Optimal Solution

Approach

The problem involves removing people in a circle until only one remains. The fastest way to solve this is by recognizing a pattern in how the winner changes as people are removed instead of directly simulating the removal process each time.

Here's how the algorithm would work step-by-step:

Start by understanding that if you only have one person, they are the winner.
With more people, determine who would have been the winner in a smaller circle.
Then, figure out how the winner from the smaller circle relates to the winner in the original, larger circle based on the removal pattern.
Continue to scale up the circle size by applying the relationship between the winners of each consecutive smaller circle to the larger circle.
Ultimately, the final winner is computed directly from the total number of people without having to simulate the whole game process.

Code Implementation

def find_the_winner(number_of_people, skip_count):
    winner = 0

    # Winner for n people can be derived from winner of n-1
    for numberOfPeople in range(2, number_of_people + 1):

        # This formula relates winner in current circle 
        # to winner in previous smaller circle
        winner = (winner + skip_count) % numberOfPeople

    # Winner index needs to be adjusted for 1-based indexing
    return winner + 1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The described approach avoids simulation and instead uses a mathematical formula derived from the pattern of winners in progressively larger circles. The core idea is to iteratively determine the winner based on the previous winner, essentially performing a constant-time calculation for each person in the circle, where 'n' is the initial number of people. This iterative process is proportional to the number of people, 'n'. Therefore, the time complexity is O(n) as we perform a fixed amount of work for each person, scaling linearly with the input size. There are no nested loops or recursion that would increase the complexity.

Space Complexity

O(1) – The algorithm determines the winner by iteratively relating the winner of a smaller circle to the winner of a larger circle through calculations, without using any auxiliary data structures like arrays, lists, or hash maps to store intermediate states or perform simulations. It solely relies on a few integer variables to keep track of the current winner derived from the calculations. Therefore, the space required remains constant irrespective of N, the number of people. The auxiliary space complexity is thus O(1).

Edge Cases

Case	How to Handle
n is 0 or negative	Return -1 or throw an exception, as a game with zero or negative players is invalid.
k is 0 or negative	Return -1 or throw an exception, as a zero or negative step size is not meaningful in this game.
n is 1	Return 1 directly, as the first player automatically wins if there's only one player.
k is 1	Return n as all players are removed sequentially until only the last player is remaining.
k is equal to n	Return n-1 as it eliminates the last player in the circle.
k is greater than n	Handle the wrap-around logic by using the modulo operator (%) to correctly calculate the next player to eliminate after each round.
Large n and k values potentially leading to integer overflow during intermediate calculations if using naive recursive approaches.	Implement the solution iteratively or use modular arithmetic with large data types to avoid overflow issues.
Extremely large n, where representing all players explicitly in a list or array becomes memory intensive	Use the Josephus problem formula or its iterative equivalent, which is optimized for space complexity, instead of simulating the entire game.