K Th Symbol In Grammar - Leetcode Solution

Problem

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 table looks like:

      0
    0  1
  0  1  1  0
0  1  1  0  1  0  0  1
At row 1, we write 0. Now in row 2, 0 occurs once and so we write 01. In row 3, 01 occurs once and 10 occurs thrice (we replace the 0 that originally occurred in the last row with 10 since 0 is present before it), so we write 0110. In row 4, 0110 occurs thrice and 1001 occurs once, so we write 01101001.
Given two integers n and k, return the kth (1-indexed) symbol in the nth row of a table of n rows.

Example 1:

Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0

Example 2:

Input: n = 2, k = 1
Output: 0
Explanation:
row 1: 0
row 2: 01

Example 3:

Input: n = 2, k = 2
Output: 1
Explanation:
row 1: 0
row 2: 01

Solution

To solve this problem, we need to understand the recursive pattern in the given pattern. We can observe that each row is dependent on its previous row. If we see the previous row or when we replace 0 with 01 and 1 with 10, we can see that the pattern is symmetric. If we reverse the previous row and replace 0 with 1 and 1 with 0, it gives us the next row. So to get the k-th symbol of nth row, we need to look at the k-th position of (n-1)th row. If the symbol at that position is 0, then the symbol at k-th position of nth row is 0. Otherwise, it will be 1.

Let's see how to implement this approach.

Pseudo Code

function constructor kthGrammar(n: integer, k:integer) -> integer if n == 1 and k == 1: return 0 mid = 2 ** (n-1) / 2 # position of middle element of previous row if k <= mid: return kthGrammar(n-1, k) else: return 1 - kthGrammar(n-1, k-mid)

Explanation of Code

We first define a function kthGrammar which takes two integer inputs n and k and returns an integer. If n is 1 and k is 1, then the first row has only 1 element which is 0, so we return 0. Otherwise, we calculate the position of the middle element in the previous row using the formula 2 ** (n-1) / 2.

Next, we check if k is less than or equal to the position of the middle element in the previous row. If it is, it means that the symbol at k-th position in the current row is the same as the symbol at the k-th position in the previous row. So we call the function recursively with n-1 and k as input and return its output.

If k is greater than the position of the middle element in the previous row, it means that the symbol at k-th position in the current row is the opposite of the symbol at the k-th position in the previous row. So we call the function recursively with n-1 and k-mid as input to get the symbol at k-mid position in the previous row. We then return 1 - the output of the recursive function as it would give us the opposite symbol.

Finally, we call the function with input n and k to get the k-th symbol of nth row.

Time Complexity: O(n) as the function makes n recursive calls.

Space Complexity: O(1) as we are not using any additional space.

1