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