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
char findKthBitRecursively(int n, int k) {
if (n == 1) return '0';
int length = (1 << n) - 1; // Length of S_n
int mid = (length + 1) / 2;
if (k == mid) return '1';
if (k < mid) return findKthBitRecursively(n - 1, k);
else {
char bit = findKthBitRecursively(n - 1, length - k + 1);
return bit == '0' ? '1' : '0';
}
}
int main() {
int n = 4, k = 11;
std::cout << "Output: " << findKthBitRecursively(n, k) << std::endl;
return 0;
}This C++ recursive approach utilizes both the structural properties and symmetry in the problem. We recursively handle the sequence split, determining appropriate transformations as needed without ever forming the entire sequence, thanks to defined recursive transitions.