LeetCode 1823 - Find the Winner of the Circular Game

The problem describes a variation of the classic Josephus problem. We have n friends sitting in a circle, numbered 1 through n clockwise. Starting from the first friend, we count k friends clockwise (inclusive of the starting friend).

leetcodemediumarraymathrecursionqueuesimulation

LeetCode Problem 1823

Difficulty: 🟡 Medium
Topics: Array, Math, Recursion, Queue, Simulation

Solution

Problem Understanding

The problem describes a variation of the classic Josephus problem. We have n friends sitting in a circle, numbered 1 through n clockwise. Starting from the first friend, we count k friends clockwise (inclusive of the starting friend). The friend at the k-th position is removed from the circle. The counting then resumes from the friend immediately clockwise of the one removed, repeating the process until only one friend remains. The task is to determine which friend is the last remaining, i.e., the winner.

The input consists of two integers: n, the number of friends, and k, the step count. The output is a single integer, the number of the winning friend. The constraints (1 <= k <= n <= 500) tell us the input size is small enough that even an O(n²) solution can be acceptable, though an O(n) solution exists using a mathematical approach.

Key edge cases include n = 1 where the first friend is trivially the winner, and cases where k = 1 which results in sequential elimination.

Approaches

Brute Force Approach

The brute-force method simulates the game directly using a list or queue. We start with a list of friends [1, 2, ..., n]. Using modular arithmetic, we count k friends, remove the k-th friend, and repeat until only one friend remains. This guarantees correctness because it directly implements the rules. However, removing elements from a list repeatedly in Python or Go takes O(n) time per removal, leading to an O(n²) total runtime.

Optimal Approach

The optimal approach leverages the Josephus problem formula. Let f(n, k) represent the winner’s position for n people and step k. The recursive formula is:

f(1, k) = 0
f(n, k) = (f(n-1, k) + k) % n  for n > 1

This formula gives a 0-indexed position, so we add 1 at the end to convert it to 1-indexed. This approach runs in linear time O(n) and constant space O(1), avoiding explicit simulation.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Simulates the elimination process using a list or queue
Optimal O(n) O(1) Uses recursive Josephus formula iteratively to find winner

Algorithm Walkthrough

  1. Initialize a variable winner to 0. This will store the zero-indexed winner as we compute recursively.
  2. Iterate i from 2 to n inclusive. At each step, update winner = (winner + k) % i. This simulates adding the next person to the circle and adjusting the winner position.
  3. After the loop completes, winner holds the zero-indexed winner for n friends.
  4. Return winner + 1 to convert from zero-based to one-based indexing.

Why it works: The Josephus recurrence ensures that at each step i, winner correctly represents the last remaining person's index in a circle of size i. By iteratively applying the formula, we avoid recursion stack overhead and directly compute the result for n.

Python Solution

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        winner = 0  # zero-indexed winner
        for i in range(2, n + 1):
            winner = (winner + k) % i
        return winner + 1  # convert to 1-indexed

This implementation initializes the winner as 0 for the base case of one person. The for loop iterates from 2 to n, incrementally building the winner for increasing circle sizes. The modulo operation ensures the circular nature of the game is respected. Finally, we add 1 to convert the result to one-based indexing as required by the problem.

Go Solution

func findTheWinner(n int, k int) int {
    winner := 0
    for i := 2; i <= n; i++ {
        winner = (winner + k) % i
    }
    return winner + 1
}

In Go, the approach is identical. The only differences are syntax: we use := for variable initialization and for i := 2; i <= n; i++ as the loop structure. Integer operations naturally handle the modulo calculation without concern for overflow due to the problem constraints.

Worked Examples

Example 1: n = 5, k = 2

Step Remaining Circle Eliminate Winner (0-indexed)
Start [1, 2, 3, 4, 5] 2 1
1 [1, 3, 4, 5] 4 1
2 [1, 3, 5] 1 1
3 [3, 5] 5 0
4 [3] 0

Final winner: 3

Example 2: n = 6, k = 5

Step Remaining Circle Eliminate Winner (0-indexed)
Start [1, 2, 3, 4, 5, 6] 5 4
1 [1, 2, 3, 4, 6] 4 3
2 [1, 2, 3, 6] 6 3
3 [1, 2, 3] 2 1
4 [1, 3] 3 0
5 [1] 0

Final winner: 1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Iterates through 2 to n, performing constant-time arithmetic operations
Space O(1) Uses a single variable to track the winner; no additional data structures are required

The optimal approach avoids list manipulations, making it linear in time and constant in space. The iterative Josephus formula is efficient even for the maximum input size n = 500.

Test Cases

# Provided examples
assert Solution().findTheWinner(5, 2) == 3  # Example 1
assert Solution().findTheWinner(6, 5) == 1  # Example 2

# Edge cases
assert Solution().findTheWinner(1, 1) == 1  # Only one person
assert Solution().findTheWinner(5, 1) == 5  # k = 1, sequential elimination
assert Solution().findTheWinner(5, 5) == 2  # k = n, full circle each time

# Larger n
assert Solution().findTheWinner(500, 2) == 341  # Stress test
assert Solution().findTheWinner(500, 500) == 318  # Large k = n
Test Why
n=5, k=2 Validates normal game simulation with small n
n=6, k=5 Checks elimination order with larger k
n=1, k=1 Single person edge case
n=5, k=1 Sequential elimination scenario
n=5, k=5 Step size equal to n, tests circular wrap-around
n=500, k=2 Stress test with maximum n
n=500, k=500 Stress test with maximum n and k

Edge Cases

Single friend: If n = 1, there is only one friend, so they are the winner. Our algorithm handles this naturally because the loop from 2 to n does not execute, and we return winner + 1 = 1.

Step size of one: When k = 1, the elimination is sequential, always removing the next friend in the circle. The Josephus formula reduces to winner = (winner + 1) % i, which correctly handles this linear elimination.

Step size equal to number of friends: If k = n, each elimination counts exactly through the full circle. The modulo operation in the iterative formula ensures wrap-around counting is handled correctly, and the algorithm produces the correct winner without simulating each step.