Chuỗi ma thuật (Magical String) trong C++

Chuỗi ma thuật S chỉ chứa '1','2' và tự sinh ra bằng cách đếm độ dài các khối liên tiếp. S = "1221121221221121122...". Tìm số ký tự '1' trong N ký tự đầu.

Ví dụ: N=6 → "122112" có 3 chữ số 1.

Thuật toán (Sinh chuỗi theo quy tắc)

1. Khởi tạo arr[0]=1, arr[1]=2, arr[2]=2.
2. head=2 (chỉ số đọc), tail=3 (chỉ số ghi), num=1 (giá trị ghi).
3. Khi :
   • Ghi arr[head] lần giá trị num vào arr[tail++].
   • Đếm số '1' ghi được.
   • num ^= 3 (xen kẽ 1↔2). head++.

Mã nguồn C++

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

class Solution {
public:
    int magicalString(int n) {
        if (n <= 0) return 0;
        if (n <= 3) return 1;
        vector arr(n);
        arr[0]=1; arr[1]=2; arr[2]=2;
        int head=2, tail=3, num=1, ret=1;
        while (tail < n) {
            for (int i=0; i= n) break;
            }
            num ^= 3;
            head++;
        }
        return ret;
    }
};

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

Đầu vào / Đầu ra

Input: 6

Output: 3