k-th-symbol-in-grammar

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

We build a table of <code>n</code> rows (1-indexed). We start by writing <code>0</code> in the <code>1st</code> row. Now in every subsequent row, we look at the previous row and replace each occurrence of <code>0</code> with <code>01</code>, and each occurrence of <code>1</code> with <code>10</code>.

<ul>
	<li>For example, for <code>n = 3</code>, the <code>1st</code> row is <code>0</code>, the <code>2nd</code> row is <code>01</code>, and the <code>3rd</code> row is <code>0110</code>.</li>
</ul>

Given two integer <code>n</code> and <code>k</code>, return the <code>kth</code> (1-indexed) symbol in the <code>nth</code> row of a table of <code>n</code> rows.

&nbsp;
Example 1:

<pre>
Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0
</pre>

Example 2:

<pre>
Input: n = 2, k = 1
Output: 0
Explanation: 
row 1: 0
row 2: 01
</pre>

Example 3:

<pre>
Input: n = 2, k = 2
Output: 1
Explanation: 
row 1: 0
row 2: 01
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 30</code></li>
	<li><code>1 &lt;= k &lt;= 2n - 1</code></li>
</ul>

kthGrammar

K-th Symbol in Grammar

Bit Manipulation

Recursion

Math

我们构建了一个包含 <code>n</code> 行(&nbsp;索引从 1&nbsp; 开始&nbsp;)的表。首先在第一行我们写上一个 <code>0</code>。接下来的每一行，将前一行中的<code>0</code>替换为<code>01</code>，<code>1</code>替换为<code>10</code>。

<ul>
	<li>例如，对于 <code>n = 3</code> ，第 <code>1</code> 行是 <code>0</code> ，第 <code>2</code> 行是 <code>01</code> ，第3行是 <code>0110</code> 。</li>
</ul>

给定行数&nbsp;<code>n</code>&nbsp;和序数 <code>k</code>，返回第 <code>n</code> 行中第 <code>k</code>&nbsp;个字符。（&nbsp;<code>k</code>&nbsp;从索引 1 开始）

 
示例 1:

<pre>
输入: n = 1, k = 1
输出: 0
解释: 第一行：0
</pre>

示例 2:

<pre>
输入: n = 2, k = 1
输出: 0
解释: 
第一行: 0 
第二行: 01
</pre>

示例 3:

<pre>
输入: n = 2, k = 2
输出: 1
解释:
第一行: 0
第二行: 01
</pre>

&nbsp;

提示:

<ul>
	<li><code>1 &lt;= n &lt;= 30</code></li>
	<li><code>1 &lt;= k &lt;= 2n - 1</code></li>
</ul>