#1823

Medium

auto_awesomeQueue-driven state processing

LeetCode Problem Workspace

Find the Winner of the Circular Game

Find the winner of a circular game by simulating the elimination process with a queue-driven approach.

Problem Statement

In a circular game, there are n friends sitting in a circle. The friends are numbered from 1 to n in clockwise order. Starting from a given position, every k-th friend is eliminated until only one remains.

Given the total number of friends, n, and the elimination step, k, you need to determine which friend will be the last remaining person, i.e., the winner of the game.

Examples

Example 1

Input: n = 5, k = 2

Output: 3

Here are the steps of the game:

Start at friend 1.
Count 2 friends clockwise, which are friends 1 and 2.
Friend 2 leaves the circle. Next start is friend 3.
Count 2 friends clockwise, which are friends 3 and 4.
Friend 4 leaves the circle. Next start is friend 5.
Count 2 friends clockwise, which are friends 5 and 1.
Friend 1 leaves the circle. Next start is friend 3.
Count 2 friends clockwise, which are friends 3 and 5.
Friend 5 leaves the circle. Only friend 3 is left, so they are the winner.

Example 2

Input: n = 6, k = 5

Output: 1

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

Constraints

1 <= k <= n <= 500

Solution Approach

Queue Simulation

Use a queue to simulate the circular elimination. Start by adding all friends to the queue, and repeatedly remove the k-th person from the front of the queue until only one person remains.

Mathematical Modeling

The problem follows a well-known pattern similar to the Josephus problem, where the position of the last remaining person can be calculated iteratively based on the elimination step, k.

Recursion Optimization

Instead of simulating each elimination step, a recursive approach can be used to compute the position of the winner, reducing the need for extra space in the simulation.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n), where n is the number of friends, since each friend is processed exactly once. The space complexity is O(1), assuming in-place updates of the circular arrangement without additional data structures beyond the queue.

What Interviewers Usually Probe

Evaluating knowledge of simulating circular structures with queues.
Tests familiarity with mathematical pattern recognition (e.g., Josephus problem).
Assesses understanding of recursion and iterative approaches for optimization.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the circular nature and treating the game as linear.
Using excessive space for simulating the elimination process.
Forgetting to correctly account for the changing start position after each elimination.

Follow-up variants

Modify the game by changing the starting position of the first elimination.
Extend the problem to handle a varying step size (k) for each round of elimination.
Alter the elimination rule to skip multiple friends at once or apply different conditions for elimination.

FAQ

How do I simulate the elimination process efficiently?

Use a queue to manage the friends and simulate the process of eliminating every k-th person. This allows you to easily update the game state after each elimination.

What is the Josephus problem and how is it related?

The Josephus problem is a well-known theoretical problem where people are arranged in a circle and eliminated every k-th person. This problem is directly related, as it uses similar elimination logic.

Can I solve this problem without using recursion?

Yes, the problem can be solved using an iterative approach, such as by using a queue to simulate the eliminations step-by-step.

What if the starting position of elimination is different?

If the starting position changes, you can adjust the queue initialization to account for this new starting point. This will affect the sequence of eliminations.

What other optimizations can I apply to the solution?

In addition to using a queue, you can apply mathematical optimizations based on the Josephus problem to compute the winner directly without simulating each elimination step.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        if n == 1:
            return 1
        ans = (k + self.findTheWinner(n - 1, k)) % n
        return n if ans == 0 else ans

Solution 2: Simulation

#### TypeScript

1

2

3

4

5

6

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        if n == 1:
            return 1
        ans = (k + self.findTheWinner(n - 1, k)) % n
        return n if ans == 0 else ans

Continue Practicing

#1799 maximize score after n operations #1878 get biggest three rhombus sums in a grid #1728 cat and mouse ii