K-th Symbol in Grammar
We build a table of n rows (1-indexed). We start by writing 0 in the 1^st 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.
Given two integers n and k, return the k^th (1-indexed) symbol in the n^th row of a table of n rows.
Example 1
Input
n = 1, k = 1Output
0The first row contains only the symbol 0.
Example 2
Input
n = 2, k = 1Output
0The first symbol in the second row, 01, is 0.
Constraints
- 1 <= n <= 30
- 1 <= k <= 2^n - 1