Explaining Solution to Kth Symbol in Grammar: The Leetcode Problem

The aim of this page📝 is to solve K-th Symbol in Grammar < LeetCode

• We build a table of n rows (1-indexed).
• We start by writing 0 in the 1st row.
• Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.
• For example, for n = 3, the 1st row is 0, the 2nd row is 01, and the 3rd row is 0110.
• Given two integers n and k, return the kth (1-indexed) symbol in the nth row of a table of n rows.

Input: n = 4, k = 7 
Output: 1 

row | value
----|---------
1   | 0
2   | 01
3   | 0110
4   | 01101001
            ^
      row==4, index==7

The solution revolves around the utilizing the idea of a binary tree.

https://playgroundai.com | the dream of a binary tree, mondrian

1. I came up with a first/brute-force idea during a forest walk — and it wonderfully shows my algorithmic illiteracy

• Of course, the result of my thinking is both ..Time Limit Exceeded error on leetcode, but here comes a brute
  ..incorrect

2. The above solution is incorrect because it is not building a table but only replaces chars

• The correct solution then is

3. I should have realized that the length of the nth row of the string is 2 to the nth-1 power

• 4th row is 01101001, this is 2 to the 3rd power, which is 8
• since you are supposed to go up to the 30th row, this would give you the string of the length 2 to the 29th power
• …which is 536870912 bytes ⟹ ~500 MB
• there is no way you are going to build 500MB large string of 0s and 1s and then select a binary value with the index that could have the value of hundreds of million
• which is what painfully stresses my algorithmic illiteracy
• so, I started reading through solutions and started with

[Java] Easy to understand solution < K-th Symbol in Grammar < LeetCode

4. I had some inkling that recursion is building a binary tree, but…

• had no idea that you can utilize the idea of the tree without the real presence of the data
• Now, you do not have the tree object at hand at all
• the initial’s example of n=4,k=7 can be visually represented as follows:

0 01 0110 01101001
             ^

• And, somehow you need to climb from the field that is given to us with coordinates to the value of that field
• The other major observation is that ..1. The value of odd positions is identical to its parent ..2. The value of even positions is opposite (flipped) to its parent
• Note that the first half of the string is identical as in the string N-1, i.e.:

row# | part     | value
-----|----------|-----------------
1    | full     | 0
2    | 1st half | 0
2    | 2nd half | 1
2    | full     | 01
3    | 1st half | 01
3    | 2nd half | 10
3    | full     | 0110
4    | 1st half | 0110
4    | 2nd half | 1001
4    | full     | 01101001
5    | 1st half | 01101001
5    | 2nd half | 10010110
5    | full     | 0110100110010110

• what are the facts

5. Let’s look into the solution

6. There is some redundancy in recursion if k is already 1

• You are reducing both, so could you modify the base case once you get to k==1?
• The attempt of the optimized base case would be

def ksym_rec(n, k):
    if n == 1 or k == 1:
        return 0

• Adding the test k == 1 makes performs worse on leet code as seems to be more expensive to test each call than to save few recursion calls

LINKS

• K-th Symbol in Grammar < LeetCode
• [Java] Easy to understand solution < K-th Symbol in Grammar < LeetCode