Class Solution
java.lang.Object
g1501_1600.s1545_find_kth_bit_in_nth_binary_string.Solution
1545 - Find Kth Bit in Nth Binary String.<p>Medium</p>
<p>Given two positive integers <code>n</code> and <code>k</code>, the binary string <code>S<sub>n</sub></code> is formed as follows:</p>
<ul>
<li><code>S<sub>1</sub> = “0”</code></li>
<li><code>S<sub>i</sub> = S<sub>i - 1</sub> + “1” + reverse(invert(S<sub>i - 1</sub>))</code> for <code>i > 1</code></li>
</ul>
<p>Where <code>+</code> denotes the concatenation operation, <code>reverse(x)</code> returns the reversed string <code>x</code>, and <code>invert(x)</code> inverts all the bits in <code>x</code> (<code>0</code> changes to <code>1</code> and <code>1</code> changes to <code>0</code>).</p>
<p>For example, the first four strings in the above sequence are:</p>
<ul>
<li><code>S<sub>1</sub> = “0”</code></li>
<li><code>S<sub>2</sub> = “0<strong>1</strong>1”</code></li>
<li><code>S<sub>3</sub> = “011<strong>1</strong>001”</code></li>
<li><code>S<sub>4</sub> = “0111001<strong>1</strong>0110001”</code></li>
</ul>
<p>Return <em>the</em> <code>k<sup>th</sup></code> <em>bit</em> <em>in</em> <code>S<sub>n</sub></code>. It is guaranteed that <code>k</code> is valid for the given <code>n</code>.</p>
<p><strong>Example 1:</strong></p>
<p><strong>Input:</strong> n = 3, k = 1</p>
<p><strong>Output:</strong> “0”</p>
<p><strong>Explanation:</strong> S<sub>3</sub> is “<strong>0</strong>111001”. The 1<sup>st</sup> bit is “0”.</p>
<p><strong>Example 2:</strong></p>
<p><strong>Input:</strong> n = 4, k = 11</p>
<p><strong>Output:</strong> “1”</p>
<p><strong>Explanation:</strong> S<sub>4</sub> is “0111001101<strong>1</strong>0001”. The 11<sup>th</sup> bit is “1”.</p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>1 <= n <= 20</code></li>
<li><code>1 <= k <= 2<sup>n</sup> - 1</code></li>
</ul>
-
Constructor Summary
Constructors -
Method Summary
-
Constructor Details
-
Solution
public Solution()
-
-
Method Details
-
findKthBit
public char findKthBit(int n, int k)
-