1823. Find the Winner of the Circular Game

Time: O(n)

Space: O(1)

Intuition

Josephus problem. Find winner when counting k positions starting from 1. Recurrence: winner(1)=0, winner(n) = (winner(n-1)+k) % n.

Algorithm

1Base: 1 person, winner=0 (0-indexed).
2For n from 2 to n: position = (position + k) % n.
3Return position + 1 (1-indexed).

Common Pitfalls

•Classic Josephus recurrence in O(n). Convert to 1-indexed at the end.

1823.cs

// Approach: Josephus problem recurrence: f(i) = (f(i-1) + k) % i, then return winner + 1.
// Time: O(n) Space: O(1)

public class Solution
{
    public int FindTheWinner(int n, int k)
    {
        int ans = 0;
        for (int i = 2; i <= n; i++)
            ans = (ans + k) % i;

        return ans + 1;
    }
}

Was this solution helpful?