# 25.10.2023 [779. K-th Symbol in Grammar]
Binary Tree `0 -> 01`, `1 -> 10` at `[n][k]` position
25.10.2023
779. K-th Symbol in Grammar medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/381
Problem TLDR
Binary Tree 0 -> 01
, 1 -> 10
at [n][k]
position
Intuition
Let’s draw the example and see the pattern:
//1 [0]
//2 [0] 1
//3 [0] 1 1 0
//4 0 [1] 1 0 1 0 0 1
//5 0 1 1 [0] 1 0 0 1 1 0 0 1 0 1 1 0
//6 0 1 1 0 1 0 [0]1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
// 1 2 3 4 5 6 7 8 9
// ^
Some observations:
Every
0
starts its own tree, and every1
start its own pattern of a tree.We can know the position in the previous row:
(k + 1) / 2
if previous value is
0
, current pair is01
, otherwise10
Approach
we don’t need to memorize the recursion, as it goes straightforward up
we can use
and 1
bit operation instead of% 2
Complexity
Time complexity:
O(n)Space complexity:
O(n)
Code
fun kthGrammar(n: Int, k: Int): Int = if (n == 1) 0 else
(if (kthGrammar(n - 1, (k + 1) / 2) == 0) k.inv() else k) and 1