S_{n-1}.

Key observations:

The midpoint of S_n is at index 2^(n-1).
The structure of each part is symmetric.

Base Case:

If n = 1, the string is "0".

Recursion:

If k equals the midpoint, return 1.
If k lies in the first half, recursively find the bit in S_{n-1}.
If k lies in the second half, find the corresponding position in the first half of S_{n-1}, compute the bit, and then invert it.

Code

[{"language":"Java","code":"class Solution {\n    public char findKthBit(int n, int k) {\n        // Base case: When n is 1, S1 is \"0\"\n        if (n == 1) {\n            return '0';\n        }\n        \n        // Calculate the length of Sn, which is 2^n - 1\n        int length = (1 << n) - 1; // Equivalent to Math.pow(2, n) - 1\n        // Calculate the midpoint position\n        int mid = (length / 2) + 1;\n        \n        // If k is the midpoint, the k-th bit is always '1'\n        if (k == mid) {\n            return '1';\n        } \n        // If k is in the first half, recursively find the bit in Sn-1\n        else if (k <

Related Tags