LeetCode Solutions

779. K-th Symbol in Grammar

Time: $O(N)$

Space: $O(N)$

			

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
  }
};
			

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
  }
}