Bit Manipulation     C++     Math     Medium     Recursion    

Problem Statement:

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 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

 

Constraints:

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

Solution:

Firstly, let us write down the pattern that emerges from the pattern 0->01, 1->10 for n=1,2,3,4,5:

 
0
01
0110
01101001
0110100110010110

We can quickly notice a pattern that given the kthGrammar(n) = kthGrammar(n-1) + complement(kthGrammar(n-1)) ie prefix remains same and complement is concatenated. So hence, given (n, k), if we are on the right half of length L, we can get its value from the complement of (n-1,k-L/2) and if in the left half, we can simply take the value from the answer for (n-1,k).

We can use this to write the following recursive solution.

 
class Solution 
{
public:
    int kthGrammar(int n, int k) 
    {
        if (n==1) return 0;
        int L = (1<<(n-1));
        if (k<=L/2) return kthGrammar(n-1, k);
        else return 1^kthGrammar(n-1, k-L/2);
    }
};