LeetCode 1823: Find the Winner of the Circular Game (Med, Java)

Problem Statement

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 1st friend.

The rules of the game are as follows:

1. Start at the 1st friend.
2. 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.
3. The last friend you counted leaves the circle and loses the game.
4. 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 left and repeat.
5. 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.

Comparison

Solution 1: LinkedList Simulation

Approach

The most intuitive approach is to simulate the entire game process:

1. Create a circular list of friends numbered 1 to n
2. Keep track of the starting position for each elimination round
3. Calculate the elimination position using modular arithmetic
4. Remove the friend at that position
5. Update the starting position for the next round
6. Repeat until only one friend remains

Implementation

class Solution {
    public int findTheWinner(int n, int k) {
        // Initialize list of N friends, labeled from 1-N
        List<Integer> circle = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            circle.add(i);
        }

        // Maintain the index of the friend to start the count on
        int startIndex = 0;

        // Perform eliminations while there is more than 1 friend left
        while (circle.size() > 1) {
            // Calculate the index of the friend to be removed
            int removalIndex = (startIndex + k - 1) % circle.size();

            // Erase the friend at removalIndex
            circle.remove(removalIndex);

            // Update startIndex for the next round
            startIndex = removalIndex % circle.size();
        }

        return circle.get(0);
    }
}

Complexity Analysis

• Time Complexity: O(n²)

  • We perform n-1 eliminations
  • Each elimination involves a remove() operation on LinkedList which takes O(n) time
  • Total: O(n) × O(n) = O(n²)

• Space Complexity: O(n)

  • We store all n friends in the LinkedList
  • No additional space beyond the input storage

Key Implementation Details

1. Modular Arithmetic: (startIndex + k - 1) % circle.size() handles the circular nature
2. Index Update: After removal, startIndex = removalIndex % circle.size() ensures we don't go out of bounds
3. LinkedList Choice: LinkedList provides O(1) removal once we have the index, but getting to that index takes O(n)

Solution 2: Josephus Problem Formula

Approach

This problem is actually the famous Josephus Problem! Instead of simulating the entire process, we can use the mathematical formula to directly calculate the winner.

The Josephus problem has a recursive formula:

• J(1, k) = 0 (base case: with 1 person, the survivor is at position 0)
• J(n, k) = (J(n-1, k) + k) % n (recursive case)

Since our problem uses 1-based indexing, we need to add 1 to the final result.

Implementation

class Solution {
    public int findTheWinner(int n, int k) {
        // Apply Josephus problem formula
        // J(1, k) = 0, J(n, k) = (J(n-1, k) + k) % n
        int result = 0;
        for (int i = 2; i <= n; i++) {
            result = (result + k) % i;
        }
        // Convert from 0-based to 1-based indexing
        return result + 1;
    }
}

Complexity Analysis

• Time Complexity: O(n)

  • Single loop from 2 to n
  • Each iteration performs constant time operations

• Space Complexity: O(1)

  • Only using a constant amount of extra space
  • No additional data structures needed

Mathematical Insight

The Josephus formula works because:

1. When we have n people, we remove one person and have n-1 people left
2. The positions shift by k places due to the counting process
3. We can relate the solution for n people to the solution for n-1 people using this shift

When to Use Each Approach

Use Simulation when:

• You need to understand the step-by-step process
• The problem has variations that break the standard Josephus pattern
• You're learning the problem for the first time

Use Josephus Formula when:

• You need optimal time and space complexity
• You're familiar with the mathematical foundation
• You're in a competitive programming context where efficiency matters

Test Cases

// Test Case 1
findTheWinner(5, 2) // Expected: 3
// Process: [1,2,3,4,5] -> [1,3,4,5] -> [1,3,4] -> [3,4] -> [3]

// Test Case 2  
findTheWinner(6, 5) // Expected: 1
// Process: [1,2,3,4,5,6] -> [1,2,3,4,6] -> [2,3,4,6] -> [2,3,6] -> [3,6] -> [3]

Conclusion

Both approaches solve the problem correctly, but the Josephus formula provides a significant optimization. The simulation approach is valuable for understanding the problem mechanics, while the mathematical solution demonstrates how recognizing classic problems can lead to elegant and efficient solutions.

For interviews, it's worth mentioning both approaches - starting with simulation to show your understanding, then optimizing with the mathematical insight if you recognize the Josephus problem pattern.