# 779. K-th Symbol in Grammar

題目：<https://leetcode.com/problems/k-th-symbol-in-grammar/>

解法：遞迴法，依照題目規則，當 n+1 時，長度會變兩倍，前半段跟原本一樣，後半段則是前面的相反(0變1，1變0)，因此可以用遞迴的方式判斷是前半段還是後半段，然後呼叫 n-1 對應的位置。

Python3：

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1:
            return 0
        if k <= 2 ** (n - 2):
            return self.kthGrammar(n - 1, k)
        else:
            return 1 - self.kthGrammar(n - 1, k - 2 ** (n - 2))

if __name__ == '__main__':
    n = 2
    k = 2

    ans = Solution().kthGrammar(n, k)
    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int kthGrammar(int n, int k) {
    if (n == 1)
        return 0;
    if (k <= pow(2, n - 2))
        return kthGrammar(n - 1, k);
    else
        return 1 - kthGrammar(n - 1, k - pow(2, n - 2));
}

int main() {
    int n = 2;
    int k = 2;
    
    int ans = kthGrammar(n, k);
    printf("%d\n", ans);
    return 0;
}

###### tags: `leetcode` `recursion` `math`