LeetCode Entry

779. K-th Symbol in Grammar

25.10.2023 medium 2023 kotlin

Binary Tree 0 -> 01, 1 -> 10 at [n][k] position

779. K-th Symbol in Grammar medium blog post substack image.png

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 every 1 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 is 01, otherwise 10

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