[LeetCode] 1545. Find Kth Bit in Nth Binary String

Ho__sing·2024년 1월 10일

C bitwise leetcode recursion

문제해결 자체 재수강

목록 보기

26/48

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));       
}