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.
1#include <iostream>
2using namespace std;
3
4int kthGrammar(int n, int k) {
5 if (n == 1) return 0;
6 int mid = (1 << (n - 2));
7 if (k <= mid) {
8 return kthGrammar(n - 1, k);
9 } else {
10 return 1 - kthGrammar(n - 1, k - mid);
11 }
12}
13
14int main() {
15 cout << kthGrammar(3, 2) << endl; // Output: 1
16 return 0;
17}The kthGrammar function is implemented recursively. It operates by halving the position k and reflecting inversions in the second half. The recursion checks if the value of k is less than or equal to the midpoint of the current row to decide which half of the previous row to reference for the value at position k in the current row.
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
class KthSymbolIterative {
public int KthGrammarIterative(int n, int k) {
int result = 0;
while (k > 1) {
if (k % 2 == 0) {
result = 1 - result;
}
k = (k + 1) / 2;
}
return result;
}
static void Main() {
KthSymbolIterative symbol = new KthSymbolIterative();
Console.WriteLine(symbol.KthGrammarIterative(3, 2)); // Output: 1
}
}This implementation uses an iterative method to find the kth symbol by checking if k is even to determine the toggle of the bit in result. The iteration continues until we reach the root or the base case.