forked from doocs / leetcode

加入 Gitee

与超过 1200万开发者一起发现、参与优秀开源项目，私有仓库也完全免费：）

克隆/下载

README_EN.md 2.71 KB

# [1545. Find Kth Bit in Nth Binary String](https://leetcode.com/problems/find-kth-bit-in-nth-binary-string)

[中文文档](/solution/1500-1599/1545.Find%20Kth%20Bit%20in%20Nth%20Binary%20String/README.md)

## Description

<p>Given two positive integers&nbsp;<code>n</code>&nbsp;and <code>k</code>,&nbsp;the binary string&nbsp;&nbsp;<code>S<sub>n</sub></code>&nbsp;is formed as follows:</p>

<ul>
	<li><code>S<sub>1</sub>&nbsp;= &quot;0&quot;</code></li>
	<li><code>S<sub><span style="font-size: 10.8333px;">i</span></sub>&nbsp;=&nbsp;S<sub><span style="font-size: 10.8333px;">i-1</span></sub>&nbsp;+ &quot;1&quot; + reverse(invert(S<sub><span style="font-size: 10.8333px;">i-1</span></sub>))</code>&nbsp;for&nbsp;<code>i &gt; 1</code></li>
</ul>

<p>Where&nbsp;<code>+</code>&nbsp;denotes the concatenation operation,&nbsp;<code>reverse(x)</code>&nbsp;returns the reversed string <font face="monospace">x,</font>&nbsp;and&nbsp;<code>invert(x)</code>&nbsp;inverts all the bits in <font face="monospace">x</font> (0 changes to 1 and 1 changes to 0).</p>

<p>For example, the first 4 strings in the above sequence are:</p>

<ul>
	<li><code>S<sub>1&nbsp;</sub>= &quot;0&quot;</code></li>
	<li><code>S<sub>2&nbsp;</sub>= &quot;0<strong>1</strong>1&quot;</code></li>
	<li><code>S<sub>3&nbsp;</sub>= &quot;011<strong>1</strong>001&quot;</code></li>
	<li><code>S<sub>4</sub> = &quot;0111001<strong>1</strong>0110001&quot;</code></li>
</ul>

<p>Return <em>the</em> <code>k<sup>th</sup></code> <em>bit</em> <em>in</em>&nbsp;<code>S<sub>n</sub></code>. It is guaranteed that&nbsp;<code>k</code>&nbsp;is valid for the given&nbsp;<code>n</code>.</p>

<p>&nbsp;</p>

<p><strong>Example 1:</strong></p>

<pre>

<strong>Input:</strong> n = 3, k = 1

<strong>Output:</strong> &quot;0&quot;

<strong>Explanation: </strong>S<sub>3</sub>&nbsp;is &quot;<strong><u>0</u></strong>111001&quot;. The first bit is &quot;0&quot;.

</pre>

<p><strong>Example 2:</strong></p>

<pre>

<strong>Input:</strong> n = 4, k = 11

<strong>Output:</strong> &quot;1&quot;

<strong>Explanation: </strong>S<sub>4</sub>&nbsp;is &quot;0111001101<strong><u>1</u></strong>0001&quot;. The 11th bit is &quot;1&quot;.

</pre>

<p><strong>Example 3:</strong></p>

<pre>

<strong>Input:</strong> n = 1, k = 1

<strong>Output:</strong> &quot;0&quot;

</pre>

<p><strong>Example 4:</strong></p>

<pre>

<strong>Input:</strong> n = 2, k = 3

<strong>Output:</strong> &quot;1&quot;

</pre>

<p>&nbsp;</p>

<p><strong>Constraints:</strong></p>

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

## Solutions

### **Python3**

```python

```

### **Java**

```java

```

### **...**

```

```

一键复制编辑原始数据按行查看历史

提交于 2021-04-22 11:34 . feat: use relative path

1545. Find Kth Bit in Nth Binary String

Description

Given two positive integers n and k, the binary string S_n is formed as follows:

S₁ = "0"
S_i = S_i-1 + "1" + reverse(invert(S_i-1)) for i > 1

Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).

For example, the first 4 strings in the above sequence are:

S₁= "0"
S₂= "011"
S₃= "0111001"
S₄ = "011100110110001"

Return the k^th bit in S_n. It is guaranteed that k is valid for the given n.

Example 1:


Input: n = 3, k = 1

Output: "0"

Explanation: S₃ is "0111001". The first bit is "0".

Example 2:


Input: n = 4, k = 11

Output: "1"

Explanation: S₄ is "011100110110001". The 11th bit is "1".

Example 3:


Input: n = 1, k = 1

Output: "0"

Example 4:


Input: n = 2, k = 3

Output: "1"

Constraints:

1 <= n <= 20
1 <= k <= 2ⁿ - 1

Solutions

Python3

Java

...

马建仓 AI 助手

尝试更多

代码解读

代码找茬

代码优化

Java

1

https://gitee.com/fdayu/leetcode.git

git@gitee.com:fdayu/leetcode.git

fdayu

leetcode

leetcode

main