Trò chơi loại trừ (Elimination Game) trong C++

Mô tả bài toán

Cho danh sách 1..n. Lặp: loại bỏ số đầu và cách một (từ trái sang), sau đó từ phải sang, xen kẽ cho đến khi còn 1 số. Tìm số còn lại.

Ví dụ: n=9 → loại: 1,3,5,7,9 → còn [2,4,6,8] → từ phải: loại 8,4 → còn [2,6] → từ trái: loại 2 → còn 6.

Giải thuật Toán học O(log n)

Theo dõi 4 biến:

• head: phần tử đầu hiện tại.
• step: khoảng cách giữa các phần tử còn lại.
• remain: số phần tử còn lại.
• left: hướng (true = trái→phải).

• Nếu left hoặc remain lẻ → head += step.
• step *= 2, remain /= 2, left = !left.

Cài đặt C++

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

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

int main() {
    Solution ob;
    cout << ob.lastRemaining(9); // 6
    return 0;
}

Độ phức tạp

• Thời gian: O(log n).
• Không gian: O(1).