Problem Description

• Problem: LeetCode 1823: Find the Winner of the Circular Game

• Description: There are n people standing in a circle, numbered from 1 to n. They play a game in which every k-th person is eliminated in a circular manner until only one person remains. The task is to find and return the number of the last remaining person.

Approach

• Idea:

  • This is a well-known problem called the Josephus problem.

  • The solution involves repeatedly removing the k-th person from the circle until only one person is left.

• Algorithm:

  1. Use a LinkedList to store numbers from 1 to n.

  2. Use a variable removeMarker to keep track of the current position to remove.

  3. Repeat the following steps until the list size becomes 1:

     • Update removeMarker to (current removeMarker+k - 1) % list size to find the index of the person to remove.

     • Remove the person at the calculated index from the list.

  4. Return the number of the last remaining person.

Code

class Solution {
    public int findTheWinner(int n, int k) {
        LinkedList<Integer> list = new LinkedList<>();
        int removeMarker = 0;
        for (int i = 0; i < n; i++) {
            list.add(i + 1);
        }

        while (list.size() > 1) {
            removeMarker = (removeMarker + k - 1) % list.size();
            list.remove(removeMarker);
        }
        return list.get(0);
    }
}

Conclusion

• Time Complexity:

  • Removing an element from a list takes O(n) time, making the overall time complexity O(n^2).

• Space Complexity:

  • We use a LinkedList to store n elements, so the space complexity is O(n).

Approach 2

• Idea:

  • Mathematically, given n and k, the index of the person to be eliminated is fixed.

  • This can be solved using reverse computation of the sequence. This is called reverse engineering of the sequence in Josephus problem.

    • Symmetry: The rule of removing every k-th person remains the same regardless of direction.

    • Circularity: The problem inherently follows circular nature, making it direction-agnostic.

• Algorithm:

  1. Initialize winner to 0, representing the 0th index.

  2. Loop from 2 to n and update the winner index by (winner + k) % current size.

  3. Return the winner index + 1 to convert 0-based index to 1-based index.

Code

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

Conclusion

• Time Complexity:

  • The loop runs n-1 times, so the time complexity is O(n).

• Space Complexity:

  • Only constant space is used, so the space complexity is O(1).

Approach 3

• Idea:

  • Similar to Approach 2, but using a recursive function to determine the winner.

• Algorithm:

  1. Base case: If n is 1, return 0.

  2. Otherwise, return (findTheWinnerRecur(n - 1, k) + k) % n.

  3. Add 1 to the result to convert from 0-based index to 1-based index.

Code

class Solution {
    public int findTheWinner(int n, int k) {
        return findTheWinnerRecur(n, k) + 1;
    }

    private int findTheWinnerRecur(int n, int k) {
        if (n == 1) return 0;

        return (findTheWinnerRecur(n - 1, k) + k) % n;
    }
}

Conclusion

• Time Complexity:

  • The recursive function is called n times, so the time complexity is O(n).

• Space Complexity:

  • The recursion depth can go up to n, requiring O(n) space.