62. the last number left in the circle

The finger of the sword Offer 62. The last number in the circle

Ideas ： mathematics

[0,1,2,3,4]

Delete the... Every time m Number , Back to ：

Fourth Backstepping ： Fill up m A place , Current array size on module 2

The third thrust ： Fill up m A place , Current array size on module

…

summary , Namely (index+m)% Current array size

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

Time complexity O(n)

Spatial complexity O(1)