Skip to content

779. K-th Symbol in Grammar 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;  // the left node
    return kthGrammar(n - 1, k / 2) == 0;          // the right node
  }
};

1
2
3
4
5
6
7
8
9
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; // the left node
    return kthGrammar(n - 1, k / 2) == 0 ? 1 : 0;         // the right node
  }
}