$0,1,…,n-1$ 这 n 个数字 $(n>0) $ 排成一个圆圈，从数字 0 开始每次从这个圆圈里删除第 $ m $ 个数字。

求出这个圆圈里剩下的最后一个数字。

样例

1
2
3

输入：n=5 , m=3

输出：3

公式推导

$$ f(n,m) = (f(n-1,m) + m) % n \ \ n = 1 时, f(1,m) = 0\ $$

解题代码

1
2
3
4
5
6
7

class Solution {
public:
    int lastRemaining(int n, int m){
        if(n== 1) return 0;
        return (lastRemaining(n-1,m) + m)%n;
    }
};

迭代解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int lastRemaining(int n, int m){
        if(n== 1) return 0;
        int s=0;
        for(int i=1;i<=n;++i) {
            s = (s+m) % i;
        }
        return s;
    }
};