LeetCode. Sword finger offer 62 The last remaining number in the circle

Title Description

0,1,···,n-1 this n Number in a circle , From numbers 0 Start , Delete the... From this circle every time m A digital （ Delete and count from the next number ）. Find the last number left in the circle .

for example ,0、1、2、3、4 this 5 Numbers make a circle , From numbers 0 Start deleting the 3 A digital , Before deleting 4 The numbers in turn are 2、0、4、1, So the last remaining number is 3.

Ideas

This is a famous mathematical problem —— Joseph ring .

The solution is directly posted here （ There is no strict mathematical proof , But it is easier to understand and remember ）

Go back in time , Start with the last situation , Push back .

Borrow the picture of a big man ：

• The last round （ It is called the n round ）, There is only one number left （ be called x） when , The total size of the array is 1,x The subscript of is 0
• n-1 In the round ,x Is safe , We draw the whole ring into an infinite straight line , It's easy to know , The starting point of this round , To x, Yes m Number , namely x There is m Number , And what is removed in this round is x The previous number . In this round x The subscript of is (m + 0) % 2（ stay x Fill the front with m Number ）, Because of the ring , Let's take a model . This round is reserved 2 Number .
• n-2 In the round , The first number of the last round was retained , explain n-1 There is m Number , And what is removed in this round is the number in front of this number . Then add m Number , be n-1 The subscript of all numbers in the wheel should be moved to the right m, So in this round x The subscript of is ,(((m + 0) % 2) + m) % 3
• …
• The first 1 round , Revert to the original state , We can work out x Subscript in initial round

class Solution {
    
    public int lastRemaining(int n, int m) {
    
        //  The subscript of the last round 
        int x = 0;
        for (int i = 2; i <= n; i++) {
    
            x = (x + m) % i;
        }
        return x;
    }
}

Formula for ：$f(n,m)=[f(n-1,m)+m]$, The boundary condition is $f(1,m)=0$

Rigorous mathematical derivation , Reference resources ： This is probably the most detailed mathematical derivation of Joseph ring you can find ！ - You know