Sponsored
Sponsored
This approach utilizes the recursive nature of the transformation of each row. We start from the nth row and trace back to see which position in the previous level gives us the current k-th position.
Time Complexity: O(n), as each recursive call reduces the problem size by a constant factor.
Space Complexity: O(n), due to the recursion stack.
1public class KthSymbol {
2 public int kthGrammar(int n, int k) {
3 if (n == 1) return 0;
4 int mid = 1 << (n - 2);
5 if (k <= mid) {
6 return kthGrammar(n - 1, k);
7 } else {
8 return 1 - kthGrammar(n - 1, k - mid);
9 }
10 }
11
12 public static void main(String[] args) {
13 KthSymbol symbol = new KthSymbol();
14 System.out.println(symbol.kthGrammar(3, 2)); // Output: 1
15 }
16}The recursive method kthGrammar divides the problem into two parts based on the midpoint of the row. If k is in the first half, it computes for the same position in the previous row; if in the second half, it computes for the position adjusted for the second half, then inverts the value.
The iterative approach to solve this problem is based on tracing the path from the kth element in the nth row back to the root (1st element of the 1st row). Depending on whether k is odd or even, we determine whether to toggle the current result bit as we move up levels until we arrive at the base case.
Time Complexity: O(n).
Space Complexity: O(1), as no additional space is used outside of constant variables.
1
This function iteratively halves k and appropriately toggles result if k is an even number. The loop finishes when k becomes 1.