Intuition

n의 최댓값이 20이기 때문에, $S_{20}$까지의 모든 문자열을 만들어 확인해보는 것이 가능하지만,
문제의 description에서 base case와 점화식이 주어지므로 재귀를 고려해볼 수 있다.

Approach

$S_n$문자열은 1이 위치한 $2^{n-1} (n\geq2)$번째 bit를 기준으로, 그 앞은 $S_{n-1}$과 동일하다.
그 뒷부분에 대해 살펴보겠다.
$2^{n-1}$번째 bit를 기준으로, $k$번째 bit까지의 거리는 $k-2^{n-1}$로 동일하다.
따라서, $S_n$의 $k$번재 비트는 $S_{n-1}$의 $2^{n-1}-(k-2^{n-1})=2^n-k$이다.그리고 해당 비트를 invert하면 된다.

$f(n,k):=$$S_n$에서 $k$번째 비트의 값
$f(n,k)=\begin{cases}f(n-1,k) & k<2^{n-1}\\1 & k==2^{n-1}\\invert(f(n-1,2^n-k))&k>2^{n-1}\end{cases}$

Base Case는 $f(1,1)=0$이다.

Solution

#define invert(a) ((a)=='0'?'1':'0')

char findKthBit(int n, int k) {
    if (n==1||k==1) return '0';

    int one=1<<(n-1);

    if(k<one) return findKthBit(n-1,k);
    if(k==one) return '1';
    else return invert(findKthBit(n-1,(one<<1)-k));       
}

Complexity

Time Compelxity & Space Complexity

$O(N)$

지적 및 질문 환영