1545. Find Kth Bit in Nth Binary String
Description
Given two positive integers n
and k
, the binary string Sn
is formed as follows:
S1 = "0"
Si = Si - 1 + "1" + reverse(invert(Si - 1))
fori > 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:
S1 = "0"
S2 = "011"
S3 = "0111001"
S4 = "011100110110001"
Return the kth
bit in Sn
. It is guaranteed that k
is valid for the given n
.
Example 1:
Input: n = 3, k = 1 Output: "0" Explanation: S3 is "0111001". The 1st bit is "0".
Example 2:
Input: n = 4, k = 11 Output: "1" Explanation: S4 is "011100110110001". The 11th bit is "1".
Constraints:
1 <= n <= 20
1 <= k <= 2n - 1
Solutions
Solution 1: Case Analysis + Recursion
We can observe that for $S_n$, the first half is the same as $S_{n-1}$, and the second half is the reverse and negation of $S_{n-1}$. Therefore, we can design a function $dfs(n, k)$, which represents the $k$-th character of the $n$-th string. The answer is $dfs(n, k)$.
The calculation process of the function $dfs(n, k)$ is as follows:
- If $k = 1$, then the answer is $0$;
- If $k$ is a power of $2$, then the answer is $1$;
- If $k \times 2 < 2^n - 1$, it means that $k$ is in the first half, and the answer is $dfs(n - 1, k)$;
- Otherwise, the answer is $dfs(n - 1, 2^n - k) \oplus 1$, where $\oplus$ represents the XOR operation.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the given $n$ in the problem.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
Solution 2: Bit Manipulation
1 2 |
|
1 |
|