C++ में व्याकरण में K-वां प्रतीक

मान लीजिए पहली पंक्ति में, हमारे पास एक 0 है। अब प्रत्येक बाद की पंक्ति में, हम पिछली पंक्ति को देखते हैं और 0 की प्रत्येक घटना को 01 से बदलते हैं, और 1 की प्रत्येक घटना को 10 से बदलते हैं। मान लीजिए हमारे पास N पंक्तियां और इंडेक्स K हैं, हमें पंक्ति N में K-वें इंडेक्स वाले प्रतीक को ढूंढना है। (K के मान 1-इंडेक्स्ड हैं।) (1 इंडेक्स्ड)। तो यदि N = 4 और K = 5, तो आउटपुट 1 होगा। ऐसा इसलिए है क्योंकि -

• पंक्ति 1: 0
• पंक्ति 2: 01
• पंक्ति 3: 0110
• पंक्ति 4: 01101001

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• मान लीजिए मेथड का नाम kthGrammar है। यह N और K लेता है।
• यदि N 1 है, तो 0 लौटाएं
• यदि k सम है, तो 1 लौटाएं जब kthGrammar(N - 1, K/2) 0 हो, अन्यथा 0
• अन्यथा kthGrammar(N - 1, (K + 1)/2) लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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);
        }
    }
};

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

इनपुट

4 5

आउटपुट

1