面试题62

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：

输入: n = 5, m = 3
输出: 3

示例 2：

输入: n = 10, m = 17
输出: 2

限制：

• 1 <= n <= 10^5

• 1 <= m <= 10^6

Solutions

1. Josephus problem

2. reference: https://blog.csdn.net/u011500062/article/details/72855826

3. suppose the index(after the dead one) of the winner in the current round is x, since the dead one in the previous round is removed, all indexes after are moved forward(with modulo) m steps, thus the index of the winner in the previous round is (x + m) % (size of previous round).

class Solution {
public:
    int lastRemaining(int n, int m) {
        int index = 0;
        // prev round has size 2.
        for (int num = 2; num <= n; num++)
            index = (index + m) % num; 

        return index;
    }
};