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

Try to represent the current (N, K) in terms of some (N-1, prevK).  What is prevK ?

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>

第K个语法符号

执行通过

错误解答

超出内存限制

超出输出限制

超出时间限制

执行出错

内部出错

编译出错

超时

Restrictions Failed

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

 * 例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。

给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）


示例 1:


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


示例 2:


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


示例 3:


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


 

提示:

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