สัญลักษณ์ที่ K ในไวยากรณ์ (K-th Symbol in Grammar) ใน C++

แถวแรก: 0 แถวถัดไป: 0→01, 1→10 หาสัญลักษณ์ที่ K (1-indexed) ในแถว N

ตัวอย่าง

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

คำอธิบาย − Row 1: 0, Row 2: 01, Row 3: 0110, Row 4: 01101001 → ตัวที่ 5 คือ 1

แนวทางการแก้ปัญหา (Recursive / Bit Count)

• สังเกต: ค่าที่ K ขึ้นอยู่กับจำนวน 1 ใน binary ของ K-1 (parity)
• หรือ recursive: N=1 → 0; K คู่ → 1 - f(N-1, K/2); K คี่ → f(N-1, (K+1)/2)
• คำตอบ = __builtin_popcount(K-1) % 2

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

#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); // 1
    return 0;
}

ผลลัพธ์

1