Code 101: K-th Symbol in Grammar

Question

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 integer n and k, return the (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 

 

Constraints:

• 1 <= n <= 30
• 1 <= k <= 2n - 1

You can find the question here.

Solution:

By reading the question we can deduce that there is some kind of structure we need to create based on the question's requirement. Few things to note here:

1. To create the structure we need to rely on previous output. So can we use recursion?
2. The structure is a tree.

After creating the structure mentioned we can deduce few more things.

1. The size of each row is double the size of previous row.
2. If we break down the row we can see that the previous row and the first half of the row is exactly same.
3. The second half of the row is the complement of the previous row

Now we will try to think of a solution keeping all these things in mind. We have previously worked on recursion solutions and we generally break it down to 3 steps.

1. Base Case (when to stop)
2. Work needed to move toward Base Case or Solution
3. Recursive Call (call ourselves)

Let's start with base case, We know that at n = 1 we have zero, lets consider column as k. So at n == 1 and k == 1 we have 0. This becomes our base case.

if (n == 1 && k == 1) return 0; 

We will skip second part and move to the 3rd step the recursion calls.

Based on observations we know that the solution depends on the previous output and the complement of previous output.

so can we write 2 recursive calls?

recursion( n-1, k ) -> when k is less the middle element
// and for the second call we need the complement of the values i.e. when the k is greator then the middle // element
recursion( n-1, k - mid) -> when k is less the middle element

Now coming to the second part. Actually while thinking of the 3rd step we kind off got the second part. I'll explain in the code below.

public static int kthGrammar(int n, int k) {
    if(n==1 && k==1) {
        return 0;
    }

    int mid = ((int) pow(2, n - 1)) / 2;

    if(k <= mid) {
        return kthGrammar(n-1, k);
    } else {
        return ( kthGrammar(n-1,k-mid)) ^ 1;
    }
}

See the code does not have anything else then what we discussed, we found mid, we called the recursion calls based on the conditions we knew.

Hope you have a better understanding now, continue with the code101 series, and you'll gain a better understanding.

#HappyCoding