K-th Symbol in Grammar

Codeflu

Leetcode

K-th Symbol in Grammar

May 26, 2022 by aAshish

Time:O(N)
Space:O(N)

      
         C++
        
           class Solution {
 public:
  int kthGrammar(int N, int K) {
    if (N == 1)
      return 0;
    if (K & 1)
      return kthGrammar(N - 1, (K + 1) / 2) != 0;  // left node
    return kthGrammar(N - 1, K / 2) == 0;          // right node
  }
};

C++
`class Solution { public: int kthGrammar(int N, int K) { if (N == 1) return 0; if (K & 1) return kthGrammar(N - 1, (K + 1) / 2) != 0; // left node return kthGrammar(N - 1, K / 2) == 0; // right node } };`

      
         JAVA
        
           class Solution {
  public int kthGrammar(int N, int K) {
    if (N == 1)
      return 0;
    if (K % 2 == 1)
      return kthGrammar(N - 1, (K + 1) / 2) == 0 ? 0 : 1; // left node
    return kthGrammar(N - 1, K / 2) == 0 ? 1 : 0;         // right node
  }
}