Elimination Game
You have a list arr of all integers in the range \([1, n]\) sorted in a strictly increasing order. Apply the following algorithm on arr:
- 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 rightmost number and every other number from the remaining numbers.
- Keep repeating the steps again, alternating left to right and right to left, until a single number remains.
Given the integer n, return the last number that remains in arr.
Example 1:
Input: n = 9
Output: 6
Explanation:
arr = [1̶, 2, 3̶, 4, 5̶, 6, 7̶, 8, 9̶]
arr = [2, 4̶, 6, 8̶]
arr = [2̶, 6]
arr = [6]
Example 2:
Input: n = 1
Output: 1
Constraints:
- 1 <= n <= \(10^9\)
题意翻译：
列表 arr 由在范围 \([1, n]\) 中的所有整数组成，并按严格递增排序。对 arr 应用如下操作：
- 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
- 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
- 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
给定整数 n，返回 arr 最后剩下的数字。
Approach:
循环且规律的操作往往都可以使用递归来解决，使用递归需要找到递归方程式。
记 f(n, l) 为从左到右消除 \([1, n]\) 后的结果， f(n, r) 为从右到左消除 \([1, n]\) 后的结果。
以 n = 6 为例，从左到右间隔消除：
f(n, l): 1̶ 2 3̶ 4 5̶ 6 => 2 4 6 = 2 * (1 2 3)
观察可以得知，从左到右消除后，剩下所有的偶数，对每个偶数除 2 可以得到一个新的长度减半且需要从右到左消除的区间。即：
\[f(n, l) = 2 * f(\dfrac{n}{2}, r)\tag{1}\]接下来只需要再找到 f(n, r) 由 f(n, l) 表达的式子就可以做到递归收敛。
同样还是上面 n = 6 的例子，这次我们对区间每一个元素做一次变换：i -> n + 1 - i
(n + 1) - f(n, l): 6̶ 5 4̶ 3 2̶ 1 => 5 3 1
观察可知，变换后右边的操作刚好是 f(n, r)，所以：
\[f(n, r) = n + 1 - f(n, l)\tag{2}\]递归方程式：
\[\left\{ \begin{array}{l} f(n, l) = 2 * f(\dfrac{n}{2}, r) \\ f(n, r) = n + 1 - f(n, l) \end{array} \right. \quad \Longrightarrow \quad f(n, l) = 2 * (\dfrac{n}{2} + 1 - f(\dfrac{n}{2}, l))\tag{3}\]可以看到该递归方程式折半收敛，速度很快，在整数范围内不存在 StackOverFlow 的风险。
最后：
class Solution {
fun lastRemaining(n: Int): Int = if (n == 1) 1 else 2 * (n / 2 + 1 - lastRemaining(n / 2))
}