Ký hiệu thứ K trong ngữ pháp C++ (K-th Symbol in Grammar)

Hàng 1: 0. Hàng sau: 0→01, 1→10. Cho N, K (1-indexed), tìm ký hiệu thứ K hàng N.

Ví dụ

Input - N=4, K=5 Output - 1

Giải thích - Hàng 1: 0; Hàng 2: 01; Hàng 3: 0110; Hàng 4: 01101001. Ký tự 5 là 1.

Phương pháp tiếp cận (Đệ quy O(log K))

• N=1 → 0
• K chẵn: ngược với ký tự cha tại (N-1, K/2)
• K lẻ: giống ký tự cha tại (N-1, (K+1)/2)

Ví dụ code C++

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

class Solution {
public:
    int kthGrammar(int N, int K) {
        if (N == 1) return 0;
        if (K % 2 == 0)
            return kthGrammar(N - 1, K / 2) == 0 ? 1 : 0;
        else
            return kthGrammar(N - 1, (K + 1) / 2);
    }
};

int main() {
    Solution ob;
    cout << ob.kthGrammar(4, 5);
    return 0;
}

Kết quả

1