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.
1using System;
2using System.Text;
3
4public class Solution {
5 public static char InvertChar(char c) {
6 return c == '0' ? '1' : '0';
7 }
8
9 public static string InvertAndReverse(string s) {
10 char[] chars = new char[s.Length];
11 for (int i = 0; i < s.Length; i++) {
12 chars[i] = InvertChar(s[s.Length - i - 1]);
13 }
14 return new string(chars);
15 }
16
17 public static char FindKthBit(int n, int k) {
18 string S = "0";
19 for (int i = 2; i <= n; i++) {
20 S = S + "1" + InvertAndReverse(S);
21 }
22 return S[k - 1];
23 }
24
25 public static void Main() {
26 int n = 4, k = 11;
27 Console.WriteLine("Output: " + FindKthBit(n, k));
28 }
29}This C# solution assembles the binary string iteratively, employing string concatenation and character array reversal and inversion to achieve the description given in the problem for Si. Utilizes char[] for efficient character manipulation.
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.