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가 짝수이면 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