Kth Symbol
Hey, Prepsters.
You will study the Kth Symbol problem today, which is a really fascinating one.
In service-based businesses like TCS, Wipro, Capgemini, Accenture, etc., you can expect these kinds of problems.
Problem Statement:
On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.
Given row number A and index B, return the Bth indexed symbol inrow A. (The values of B are 1-indexed.).
Problem Constraints:
1 <= A <= 20 1 <= B<= 2A-1
Input Format:
First argument is an integer A. Second argument is an integer B.
Output Format:
Return an integer denoting the Bth indexed symbol in row A.
Example Input :
Input 1:
A = 2
B = 1
Output 1:
0
Input 2:
A = 2
B = 2
Output 2:
1
Explanation 1:
Row 1: 0
Row 2: 0 1
Explanation 2:
Row 1: 0
Row 2: 0 1
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int kthGrammar(int n, int k) {
if(n==1&&k==1)return 0;
int len=pow(2,n-1);
int mid=len/2;
if(k<=mid){
return kthGrammar(n-1,k);
}
else{
return !(kthGrammar(n-1,k-mid));
}
}
int main()
{
int n,k;
cin>>n>>k;
cout<<kthGrammar(n,k)<<endl;
return 0;
}
For similar questions click on the given button.
