เกมการตัดตัวเลขใน C++

มีรายการตัวเลข 1 ถึง n เรียงจากซ้ายไปขวา ทำซ้ำ: 1) ตัดจากซ้าย: ลบตัวแรกและทุกตัวคู่ (1,3,5...) 2) ตัดจากขวา: ลบตัวสุดท้ายและทุกตัวคู่จากขวา สลับด้านจนเหลือ 1 ตัว หาตัวสุดท้าย

ตัวอย่าง: n=9 → 1,2,3,4,5,6,7,8,9 → (ซ้าย) 2,4,6,8 → (ขวา) 2,6 → (ซ้าย) 6 → คำตอบ 6

ขั้นตอนการแก้ปัญหา (Mathematical Pattern)

1. head = 1, step = 1, remaining = n, left = true
2. วนจน remaining > 1:
   • ถ้า left หรือ remaining คี่ → head += step
   • step *= 2
   • left = !left
   • remaining /= 2
3. คืน head

ไอเดีย: ตัวแรกของแต่ละรอบ (head) เปลี่ยนก็ต่อเมื่อตัดจากซ้าย หรือตัดจากขวาแต่จำนวนคี่

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int lastRemaining(int n) {
        int head = 1, step = 1, rem = n, left = 1;
        while (rem > 1) {
            if (left || rem % 2 == 1) head += step;
            step *= 2;
            left = !left;
            rem /= 2;
        }
        return head;
    }
};

int main() {
    Solution ob;
    cout << ob.lastRemaining(9);
}

Input

9

Output

6