# LeetCode 1823. Find the Winner of the Circular Game

https://leetcode.com/problems/find-the-winner-of-the-circular-game/description/

## 題目大意

所有人圍成圓圈從 `1` 開始叫號，數到 `k` 就把那個倒楣蛋踢出去
直到最後剩一人時遊戲結束，回傳該名勝者的號碼

## 思考

這題就 [Josephus problem](https://en.wikipedia.org/wiki/Josephus_problem#The_general_case) ，用數學推導一下就能得出結論
不過這邊也不必這麼正式

反正就想成每次叫號都會 `+k` 沒被叫到的傢伙已經回蘇州賣鴨蛋了
然後這群傢伙是圍成一圈的，取 mod 就能一直叫號叫到只剩一人

假設所求表示成 $f(n,k)$ 那麼可以總結 $f(n,k) = (f(n-1,k) + k) \mod n$

得出遞迴式了你當然直接翻成 `C++` 就能交卷
但你也可以把它改成非遞迴寫法

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;
    }
};