[LeetCode] 390. Elimination Game

😎풀이

1. 매 반복마다 남은 요소의 수는 절반이 됨
2. 정답 요소는 첫 요소로부터 한 번은 이동(좌 -> 우), 한 번은 정지(우 -> 좌)하는 형식 가장 좌측의 요소로 남음
   2-1. 단, 요소가 홀 수개 남은 경우 반드시 이동해야함 (가장 좌측의 요소가 반드시 사라짐)
3. 이동 간격은 매 시점마다 절반의 요소가 사라지므로 2배씩 이동해야함
4. 최종적으로 요소가 한 개 남았을 때 가장 좌측의 요소의 값이 마지막 요소의 값임

function lastRemaining(n: number): number {
    let curr = 1
    let remain = n
    let toRight = true
    let step = 1
    while(remain > 1) {
        if(toRight || (remain & 1) === 1) curr += step;
        remain = Math.floor(remain / 2)
        step *= 2
        toRight = !toRight
    }
    return curr
};