题目描述

给定两个正整数 n 和 k，二进制字符串 $S_n$ 的形成规则如下：

• $S_1 = “0”$
• 当 $i > 1$ 时，$S_i = S_{i-1} + “1” + reverse(invert(S_{i-1}))$

其中 + 表示串联操作，$reverse(x)$ 返回反转 $x$ 后得到的字符串，而 $invert(x)$ 则会翻转 $x$ 中的每一位（0 变为 1，而 1 变为 0）

例如，符合上述描述的序列的前 4 个字符串依次是：

• $S_1 = “0”$
• $S_2 = “011”$
• $S_3 = “0111001”$
• $S_4 = “011100110110001”$

请你返回 $S_n$ 的 第 $k$ 位字符，题目数据保证 $k$ 一定在 $S_n$ 长度范围以内。

样例

输入：n = 3, k = 1
输出："0"
解释：S3 为 "0111001"，其第 1 位为 "0"。

输入：n = 4, k = 11
输出："1"
解释：S4 为 "011100110110001"，其第 11 位为 "1"。

输入：n = 1, k = 1
输出："0"

输入：n = 2, k = 3
输出："1"

限制

• 1 <= n <= 20
• 1 <= k <= 2^n - 1

算法

(折半搜索) $O(n)$

1. 在 $n > 1$ 时，每次判断出 $k$ 所在的位置输入左半部分还是右半部分，或者正中间。$ans$ 初始化为 $0$。
2. 如果 $k$ 在正中间，则返回 $ans \text{ xor } 1$。
3. 如果 $k$ 在左半部分，$n$ 减少 1，$k$ 和 ans 都不需要变化。
4. 如果 $k$ 在右半部分，则相当于 $k$ 在 $S_{n-1}$ 的 $2^n - k$ 位置，则 $n$ 减少 1，$k = 2^n - k$，$ans = ans \text{ xor } 1$。
5. 最后 $n == 1$ 时返回 $ans$。

时间复杂度

• 每次 $n$ 都会减少 1，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

Go 代码

func findKthBit(n int, k int) byte {
    var ans byte

    for n > 1 {
        if k * 2 == 1 << n {
            ans ^= 1
            break
        }

        if k * 2 < 1 << n {
            n--
        } else {
            k = (1 << n) - k
            n--;
            ans ^= 1
        }
    }

    return ans + '0'
}