Leecode learning notes - Joseph problem

class Solution {
    
    public int lastRemaining(int n, int m) {
    
        int ans = 0;
        //  The rest of the last round 2 personal , So from 2 Start backstepping 
        for (int i = 2; i <= n; i++) {
    
            ans = (ans + m) % i;
        }
        return ans;
    }
}

• explain

Help you understand
problem 1： Suppose we already know 11 Personal time , The subscript position of the winner is 6. Then the next round 10 Personal time , What is the subscript position of the winner ？
answer ： In fact! , The first round of deletion is numbered 3 After , After that, everyone moved forward 3 position , Victory is also moving forward 3 position , So his subscript position is determined by 6 become 3.

problem 2： Suppose we already know 10 Personal time , The subscript position of the winner is 3. Then the next round 11 Personal time , What is the subscript position of the winner ？ answer ：
This can be mistaken as the reverse process of the previous problem , Everyone moves back 3 position , therefore f ( 11 , 3 ) = f ( 10 , 3 ) + 3
f(11,3)=f(10,3)+3f(11,3)=f(10,3)+3. However, it is possible that the array will cross the boundary , So the number of current people on the final module ,f ( 11 , 3
) = （ f ( 10 , 3 ) + 3 ） % 11
f(11,3)=（f(10,3)+3）%11f(11,3)=（f(10,3)+3）%11

There is only one element left , Suppose this last surviving element is num, The final subscript of this element must be 0 （ Because there is only one element left ）,
So if we can launch this in the last round num The subscript , Then according to the previous round num The subscript of infers the previous round num The subscript ,
Until it is inferred that the number of elements is n The round of num The subscript , Then we can get the final element according to this subscript . The inference process is as follows ：
First, in the last round num The subscript of must be 0, This is known .
There should be two elements in the last round , In this round num The subscript of is (0 + m)%n = (0+3)%2 = 1; Explain before this round of deletion num The subscript of is 1;
Another round should have 3 Elements , In this round num The subscript of is (1+3)%3 = 1; It indicates that before an element is deleted in this round num The subscript of is 1;
Another round should have 4 Elements , In this round num The subscript of is (1+3)%4 = 0; It indicates that before an element is deleted in this round num The subscript of is 0;
Another round should have 5 Elements , In this round num The subscript of is (0+3)%5 = 3; It indicates that before an element is deleted in this round num The subscript of is 3;
…

Because the sequence we want to delete is 0-n-1, So getting the subscript is actually getting the final result . For example, when n by 5 When ,num The initial subscript of is 3,
therefore num Namely 3, That is to say, from 0-n-1 In the sequence of , after n-1 Elimination of round ,3 This element finally survived , It is also the final result .

Summarize the derivation formula ：( After this round num Subscript + m) % Number of elements in the last round = Last round num The subscript