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 <stdio.h>
2
3int kthGrammar(int n, int k) {
4 if (n == 1) return 0;
5 int mid = (1 << (n - 2));
6 if (k <= mid) {
7 return kthGrammar(n - 1, k);
8 } else {
9 return 1 - kthGrammar(n - 1, k - mid);
10 }
11}
12
13int main() {
14 printf("%d\n", kthGrammar(3, 2)); // Output: 1
15 return 0;
16}The function kthGrammar is defined recursively. For each call, it checks if n is 1, in which case it returns 0 since the first row is always 0.
Otherwise, it calculates the midpoint, which is 2^(n-2). It then compares k with this midpoint to determine whether to explore the first half (which is the same as the previous row) or the second half (which is the inverse of the previous 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#include <iostream>
using namespace std;
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;
}
int main() {
cout << kthGrammarIterative(3, 2) << endl; // Output: 1
return 0;
}This code snippet iteratively adjusts result based on whether the current index is in the left or the right subtree. At each step, we also adjust k upward until the top of the tree is reached (i.e., k = 1).