Title:

The N numbers 0,1, ····, n-1 are arranged in a circle, starting from the number 0, and the m-th number is deleted from the circle each time (counting from the next number after deletion). Find the last number left in the circle.

For example, the five numbers 0, 1, 2, 3 and 4 form a circle. Starting from the number 0, delete the third number each time, then the first four deleted numbers are 2, 0, 4 and 1 in turn, so the last remaining number is 3.

Example 1:

input: n = 5, m = 3
 output: 3

Example 2:

input: n = 10, m = 17
 output: 2

Restrictions:

1 <= n <= 10^5
1 <= m <= 10^6

Extension:

This question is the classic Joseph problem:

People stood in a circle waiting to be executed. Counting starts at a specified point in the circle and goes around the circle in a specified direction. After skipping a specified number of people, execute the next person. Repeat the process for the remaining people, starting with the next person and skipping the same number of people in the same direction until only one person is left and released.

The problem is that given the number of people, starting point, direction and number to skip, choose the position in the initial circle to avoid execution.

The question is named after Flavio Joseph, a Jewish historian in the first century. He wrote in his diary that he and his 40 comrades in arms were surrounded by the Roman army in the cave. They discussed whether to commit suicide or be captured, and finally decided to commit suicide and decide who to kill by drawing lots. Josephus and the other man were the last two to stay. Josephus persuaded the man that they would surrender to the Roman army and not commit suicide. Josephus attributed his survival to luck or providence. He didn't know which one.

Solution 1: Violence

    /**
     * Idea:
     * Create a boolean array of length n. if the array value is false, it means it is not deleted, and if true, it means it is deleted
     * The created variable count represents the number of remaining elements, and the variable mark represents the current tag of each element
     * As long as the element has not reached 1, it will loop all the time
     *      Traverse the array to find the element to delete
     *      If the current subscript value is true, the element has been deleted and ignored
     *      Otherwise, mark increases. If mark is equal to m we are looking for, delete it. After that, reset the mark and count by one
     * Finally, traverse the array to find the only remaining element with false
     */
    public static int lastRemaining(int n, int m) {
        int count=n,mark=0;
        boolean[] arr=new boolean[n];
        while (count!=1){
            for (int i=0;i<n;i++){
                if (arr[i]==true){
                    continue;
                }else {
                    mark++;
                    if (mark==m){
                        arr[i]=true;
                        mark=0;
                        count--;
                    }
                }
                if (count==1){
                    break;
                }
            }
        }
        for (int i=0;i<n;i++){
            if (arr[i]==false){
                return i;
            }
        }
        return -1;
    }

Time complexity: On^2

Space complexity: On

Solution 2: linked list

    /**
     *Idea:
     * The created variable size represents the number of nodes in the linked list, and the variable mark represents the current tag of each element
     * Create a linked list to record all elements
     * If the number of nodes in the linked list is not equal to one, it will continue to cycle
     *      Traverse the linked list. When mark is equal to m, delete the node, reset the mark, and reduce the size by one
     * Returns the remaining node values
     */
    public static int lastRemaining(int n, int m) {
        int mark = 0, size = n;
        ArrayList<Integer> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        LinkedList<Integer> linked = new LinkedList<>(list);
        while (size!=1) {
            Iterator<Integer> iterator = linked.iterator();
            while (iterator.hasNext()) {
                mark++;
                //Move element
                iterator.next();
                if (mark == m) {
                    iterator.remove();
                    mark = 0;
                    size--;
                }
                if (size == 1) {
                    break;
                }
            }
        }
        return linked.get(0);
    }

Time complexity: On^2

Space complexity: On

Solution 3: Mathematics

    /**
     *Idea:
     * lastRemaining(5,3)Basic information
     * 01234
     * 3401
     * 134
     * 13
     * 3
     * After deleting one element at a time, it is equivalent to moving the whole array forward by 3
     * Push back the last surviving subscript. On the contrary, each time is equivalent to the overall backward movement of the array by 3. Considering the cross-border problem, the module is based on the current length
     * 3        (0+3)%2=1
     * 13       (1+3)%3=1
     * 134      (1+3)%4=0
     * 3401     (0+3)%5=3
     * 01234
     * Get the formula: x=(x+m)%i
     */
    public static int lastRemaining(int n, int m) {
        int x = 0;
        for (int i = 2; i <= n; i++) {
            x = (x + m) % i;
        }
        return x;
    }

Time complexity: On

Space complexity: O1