मान लीजिए कि पहली पंक्ति में, हमारे पास 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
