1545. Find Kth Bit in Nth Binary String

Medium

786

51

Given two positive integers `n`

and `k`

, the binary string `S`

is formed as follows:_{n}

`S`

_{1}= "0"`S`

for_{i}= S_{i - 1}+ "1" + reverse(invert(S_{i - 1}))`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 four strings in the above sequence are:

`S`

_{1 }= "0"`S`

_{2 }= "0**1**1"`S`

_{3 }= "011**1**001"`S`

_{4}= "0111001**1**0110001"

Return *the* `k`

^{th}*bit* *in* `S`

. It is guaranteed that _{n}`k`

is valid for the given `n`

.

**Example 1:**

Input:n = 3, k = 1Output:"0"Explanation:S_{3}is "111001". The 10^{st}bit is "0".

**Example 2:**

Input:n = 4, k = 11Output:"1"Explanation:S_{4}is "01110011010001". The 111^{th}bit is "1".

**Constraints:**

`1 <= n <= 20`

`1 <= k <= 2`

^{n}- 1

Accepted

34.1K

Submissions

58.2K

Acceptance Rate

58.6%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved