# LeetCode 1545. Find Kth Bit in Nth Binary String

https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/description/

## 題目大意

初始字串 `S_1 = '0'`
那之後符合 `S_i = S_{i - 1} + "1" + reverse(invert(S_{i - 1}))`

reverse 就是整個整個字串反轉、 invert 是邏輯反轉 (`'1'` 變 `'0'`， `'0'` 變 `'1'`)

我們要求 `S_n` 字串中的第 `k` 個字符 (index 從 1 開始的第 k 個)

## 思考

首先思考，這題已經給了遞迴表達式，這應該會對解題有某種幫助
如果設 `S_n.length()` 為 $\mathcal{l}_n$ ，則按照遞迴表達我們知道 $\mathcal{l}_n = 2\cdot\mathcal{l}_{n-1} + 1$

我們可以想通：
1. `S_n` 的長度必為奇數
2. `S_n` 的中間是只有一個 (由上可知)，而且不考慮 `S_1` 的話一定是 `'1'` (根據遞迴表達)

這樣的情況想到什麼了？沒錯，我們可以使用 binary search 的概念去求出所求

C++:

class Solution
{
public:
    char findKthBit(int n, int k)
    {
        if (n == 1)
            return '0';

        const int len = (1 << n) - 1;
        const int mid = len / 2 + 1;

        if (k == mid)
            return '1';
        if (k < mid)
            return findKthBit(n - 1, k);
        return '1' - findKthBit(n - 1, len - k + 1) + '0';
    }
};

Go:

func findKthBit(n int, k int) byte {
	if n == 1 {
		return '0'
	}

	length := (1 << n) - 1
	mid := length/2 + 1

	if k == mid {
		return '1'
	}
	if k < mid {
		return findKthBit(n-1, k)
	}
	return '1' - findKthBit(n-1, length-k+1) + '0'
}