LC1582: Find Kth Bit in Nth Binary String

Date: 2026-03-03
Difficulty: MEDIUM
Attempts: 2
Solution link: https://leetcode.com/submissions/detail/1936561504/
Question link: https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/description/

First, I simulate. Second attempt is what recorded here.

Intuition

At first I planned to hardcode the string to look up and save time of computing. But turn out that I won’t be able to even submit my question. If n=20, then I will have to store from $S_{1}$ to $S_{20}$, and just $S_{20}$ alone have 1.048.575 bits. If I still insist to go down this part, I will need to compress the hardcoded solution somehow so I gave up.

I pulled out my notebook and a pencil, try to write down the position of each individual character. I concluded that it’s possible to track the position backward to the string before by basically running the algorithm in reverse, and depend on the curren position is in the latter half of the string or not, you need to either flip the bit or keep it as is.

The tricky thing here is that to determine the position is in the first or latter half, you need to know the length of $S_{n}$.

The recipe the question give here is $S_{i}=S_{i-1}+1+invert(reverse(S_{i-1}))$. Since reverse and invert operation don’t change the length, you can conclude that $length(S_{i}) = 2*length(S_{i-1})+1$.

Now what? Doesn’t this means we need to have a loop from 1 to n to calculate the length of $S_{n}$.

Turn out. No need.

Let’s see the length of the first few strings here.

Can you see it? Let’s compare it to the table below

Recognize the pattern now?

Turn out that $length(S_{n})=P_{n}-1=2^n-1$. You don’t even need to calculate $length(S_{n-1})$ at all.

Now that we have all the ingredients we need to begin cooking.

Approach

1. If the input k is 1, we can just return 0 because the first bit will always be 0.
2. We test if the position k is in the latter half of the string or not.
3. If it’s not, then we keep k as is. If it do, then k = s.length() - k.
4. Call itself with the new k and n-1.
5. Depends on the outcome of step 2. If k was larger than half the string, then we flip the result of the call at 4.
6. Return the result of the call.

Complexity

Time complexity: $O(n)$
This is a recursive solution. Each round run a few constant-time $O(1)$ operations. In the worst case scenario, number of recursive calls will be the same as $n$ in the input, thus $O(n)$.

Space complexity: $O(n)$
The main contributor is also recursive call, what happens here is the same as time complexity.

Code

class Solution {
    public char findKthBit(int n, int k) {
        if (k == 1) {
            return '0';
        }
        int length = (1 << n) - 1;
        int half = (length / 2) + 1;
        if (k == half) {
            return '1';
        } else {
            if (k > half) {
                k = length - k + 1;
                char result = findKthBit(n - 1, k);
                return result == '1' ? '0' : '1';
            } else {
                return findKthBit(n - 1, k);
            }
        }
    }
}

Note

It’s possible to eliminate the recursive call, but complexity will still be the same so I leave it as is. If this were a real life project, I will try to eliminate the recursive call stack.