C++-এ K-তম সিম্বল ইন গ্রামার সমস্যা সমাধান

মান করুন প্রথম সারিতে আমাদের একটি 0 আছে। এখন প্রতিটি পরবর্তী সারিতে, আমরা পূর্বের সারিটি দেখি এবং প্রতিটি 0 কে 01 দিয়ে এবং প্রতিটি 1 কে 10 দিয়ে রিপ্লেস করি। ধরুন আমাদের N সারি এবং ইনডেক্স K দেওয়া আছে, আমাদের সারি N-এ K-তম ইনডেক্সের সিম্বল খুঁজে বের করতে হবে। (K-এর মান ১-ইনডেক্সড।) (১-ইনডেক্সড)।

যদি N = 4 এবং K = 5 হয়, তবে আউটপুট হবে ১। কারণ −

সারি 1: 0
সারি 2: 01
সারি 3: 0110
সারি 4: 01101001

এটি সমাধান করার জন্য নিচের ধাপগুলি অনুসরণ করুন −

মেথডের নাম ধরুন kthGrammar. এটি N এবং K নেয়।
যদি N = 1 হয়, তবে 0 ফেরত দিন
যদি K জোড় হয়, তবে kthGrammar(N - 1, K/2) == 0 ? 1 : 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