1545. Find Kth Bit in Nth Binary String

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

1. Use recursion:

//0 ms    6.2 MB
class Solution {
public:
    char findKthBit(int n, int k) {
        int kth = findChar(n,k);
        return (kth + '0');
    }
private:
    int findChar(int n,int k) {
        if(n==1 || k==1)
            return 0;
        int len = pow(2,n) - 1;
        int mid = len/2;
        if(mid+1 == k)
            return 1;
        if(k<=mid){
            return findChar(n-1,k);
        }
        else{
            return !findChar(n-1, (len-k+1));
        }
    }
};