Sponsored
Sponsored
This approach involves directly simulating the sequence construction up to the desired nth binary string and retrieving the k-th bit from it. Since the problem ensures n and k are constrained, this method remains efficient enough.
Time Complexity: O(2^n), as each step fully constructs the sequence of size approximately 2^n.
Space Complexity: O(2^n), owing to storing the full sequence.
1#include <stdio.h>
2#include <string.h>
3
4char invertChar(char c) {
5 return c == '0' ? '1' : '0';
6}
7
8void reverseString(char* str, int n) {
9 for (int i = 0; i < n / 2; i++) {
10 char temp = str[i];
11 str[i] = str[n - i - 1];
12 str[n - i - 1] = temp;
13 }
14}
15
16void invertString(char* str, int n) {
17 for (int i = 0; i < n; i++) {
18 str[i] = invertChar(str[i]);
19 }
20}
21
22char findKthBit(int n, int k) {
23 char S[1048576] = "0"; // S_n max length is 2^20 - 1
24 int currentLength = 1;
25
26 for (int i = 2; i <= n; i++) {
27 int len = currentLength;
28 S[len] = '1';
29
30 for (int j = 0; j < len; j++) {
31 S[len + 1 + j] = invertChar(S[len - 1 - j]);
32 }
33
34 currentLength = 2 * len + 1;
35 }
36
37 return S[k - 1];
38}
39
40int main() {
41 int n = 4, k = 11;
42 printf("Output: %c\n", findKthBit(n, k));
43 return 0;
44}The solution constructs each sequence iteratively using the relationship: Si = Si-1 + '1' + reverse(invert(Si-1)). We manage a buffer array S that stores each sequence step-by-step until Sn is reached, whereupon we simply return the k-th position.
This approach leverages the recursive nature and mathematical properties of the sequence to find the k-th bit without constructing the entire string. By recognizing the symmetry and structure, we use recursive calculations to directly determine the desired bit.
Time Complexity: O(n), limited by the recursion depth of n.
Space Complexity: O(n), due to recursive call stack.
1
This Python solution purely uses recursion to determine when a desired bit falls based on cycle splitting and transformations. Repeatedly computes the k-bit recursively by centering decisions around middle positions effectively.