Elimination Game 390

Question

There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:

Input:

n = 9,

1 2 3 4 5 6 7 8 9

2 4 6 8

2 6

6

Output:

6

Solution

这道题需要观察数字变化的规律：

每轮删除的数字个数为所有数字个数/2（从左往右或者从右往左都算1轮）。

有两种情况会改变开头元素，1）从左往右删除时 2）从右往左删除同时所有数字个数为奇数时。因此只要记录并更新开头元素，则最后当剩下数字个数为1时的开头元素即为剩下的最后一个元素。开头元素更新的步长随着删除的轮数发生变化，以上面的例子来说，第一次为1（1->2），第二次为2（但是从右往左且2，4，6，8一共4个数字为偶数所以开头元素没有被删除，不更新开头），第三次为4(2->6)，因此步长在每一轮之后更新为原来的2倍。

代码如下：

public class Solution {
    public int lastRemaining(int n) {
        int size = n;
        int step = 1;
        int head = 1;
        boolean left = true;

        while (size > 1) {
            if (left || size % 2 == 1) {
                head = head + step;
            }

            size /= 2;
            left = !left;
            step *= 2;
        }
        return head;
    }
}