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.
1public class Solution {
2 public static char invertChar(char c) {
3 return c == '0' ? '1' : '0';
4 }
5
6 public static String invertAndReverse(String s) {
7 StringBuilder sb = new StringBuilder();
8 for (int i = s.length() - 1; i >= 0; i--) {
9 sb.append(invertChar(s.charAt(i)));
10 }
11 return sb.toString();
12 }
13
14 public static char findKthBit(int n, int k) {
15 String S = "0";
16 for (int i = 2; i <= n; i++) {
17 S = S + "1" + invertAndReverse(S);
18 }
19 return S.charAt(k - 1);
20 }
21
22 public static void main(String[] args) {
23 int n = 4, k = 11;
24 System.out.println("Output: " + findKthBit(n, k));
25 }
26}The Java solution uses iterative String construction using a StringBuilder for efficient string manipulation while translating the form: Si = Si-1 + '1' + reverse(invert(Si-1)). This approach continues until building the entire Sn chain.
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
public class SolutionRecursive {
public static char FindKthBitRecursively(int n, int k) {
if (n == 1) return '0';
int length = (1 << n) - 1; // S_n length
int mid = (length + 1) / 2;
if (k == mid) return '1';
if (k < mid) return FindKthBitRecursively(n - 1, k);
else {
return FindKthBitRecursively(n - 1, length - k + 1) == '0' ? '1' : '0';
}
}
public static void Main() {
int n = 4, k = 11;
Console.WriteLine("Output: " + FindKthBitRecursively(n, k));
}
}This C# technique solely utilizes recursive manipulation concepts outlined within the reverse, contract, and determine pattern. Attains resultant k-bit via stepwise recursive deviations without constructing each sequence in entirety.