> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/06-14-2022-779.-k-th-symbol-in-grammar.md).

# 06/14/2022 779. K-th Symbol in Grammar

need to observe

recurrence relation:

Method: to compare k and the length of the current n row. If k is greater than the half the length, we call recursively the function with n-1 and k - length/2. When we get the val, if it is 0, we filpped it to 1 and vice versa. If k is less than the half the lenght, we call ecursively the function with n-1 and k and return this val. 

Time O(N)

Space O(N)