1823. Find the Winner of the Circular Game 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findTheWinner(int n, int k) {
        if (n == 1) {
            // 当只有一个元素时，直接返回该元素
            return 1;
        }

        // 设 n = 10, k = 3
        // 可知：f(10, 3) 的计算过程如下：
        // 1 2 3 4 5 6 7 8 9 10: 准备消除第 3 个元素
        //       4 5 6 7 8 9 10 1 2: 此为消除第 3 个元素后的排列
        // 我们知道 f(9, 3) 的初始排列如下：
        // 1 2 3 4 5 6 7 8 9, 易推导出：f(10, 3) = (f(9, 3) + 3) % 10
        // 即推导出计算递推公式：f(n, k) = (f(n - 1, k) + k) % n
        // 注意 (7 + 3) % 10 = 0, 此时需要调整为 10
        int tmp = (findTheWinner(n - 1, k) + k) % n;
        return tmp == 0 ? n : tmp;
    }
}

References

1823. Find the Winner of the Circular Game
约瑟夫环问题的三种解法讲解