https://leetcode.com/problems/elimination-game/

// 一行代码就可以，不过原理有些复杂

// https://discuss.leetcode.com/topic/58042/c-1-line-solution-with-explanation

// return n == 1 ? 1 : 2 * (1 + n / 2 - lastRemaining(n / 2));

// https://discuss.leetcode.com/topic/59293/easiest-solution-o-logn-with-explanation

public class Solution {

    public int lastRemaining(int n) {

        boolean isLeft = true;

        int left = n;

        int step = 1;

        int head = 1;

        while (left != 1) {

            if (isLeft || left % 2 == 1) {

                head += step;

            }

            step *= 2;

            left /= 2;

            isLeft = !isLeft;

        }

        return head;

    }

}