How to find K-th symbol in Grammar using C++

In the problem, we build a table of n rows (1-indexed). We start by using writing zero within the 1st row. Now in every subsequent row, we observe the preceding row and replace each occurrence of zero with 01, and every incidence of one with 10.
As an example,for n = 4,the 1st row is 0,the second row is 01,the 3rd row is 0110,and the 4th row is 01101001.
we will take n and k as input and return K-th symbol in nth row of table.

K-th symbol in Grammar using C++

For this problem, we will take a recursive approach. In each consecutive row, we can observe the repeating pattern. Elements before the middle element in each row is similar to the entire element in the previous row and the element after the middle element is NOT of elements in the previous row. And in each next row the number of elements get doubled.
1-> 0
2-> 1 0
3-> 0 1 1 0
4-> 1 0 0 1 0 1 1 0
So for nth row,mid(index of middle element)=2^(n-1)/2. And if K<mid then we will return Kth element previous row. And if K>mid, then NOT of (K-mid) element of the previous row will be answered.

#include<bits/stdc++.h>
using namespace std;
int kthGrammar(int n, int k) {
        if(n==1 && k==1)
            return 0;
        int mid=pow(2,n-1)/2;
        if(k<=mid)
        {
            return kthGrammar(n-1,k);
            
        }
        return !kthGrammar(n-1,k-mid);
}
int main(){
     int n,k;
     cin>>n>>k;
     cout<<kthGrammar(n,k);
}
input:
n=4,k=5
output:1

Also read: C++ program to find Kth permutation Sequence

Leave a Reply

Your email address will not be published. Required fields are marked *