K-th Symbol in Grammar
MedPrompt
We build a table of n rows (1-indexed). We start by writing 0 in the 1st row. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.
- For example, for
n = 3, the1strow is0, the2ndrow is01, and the3rdrow is0110.
Given two integer n and k, return the kth (1-indexed) symbol in the nth row of a table of n rows.
Example 1:
Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0Example 2:
Input: n = 2, k = 1
Output: 0
Explanation:
row 1: 0
row 2: 01Example 3:
Input: n = 2, k = 2
Output: 1
Explanation:
row 1: 0
row 2: 01
Constraints:
1 <= n <= 301 <= k <= 2n - 1
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. We start with the string for the first row, "0", and iteratively generate the string for each subsequent row up to n. This method is straightforward but computationally expensive.
Algorithm
- Initialize a string
currentRowto "0". - Loop from
i = 2ton. - Inside the loop, create a
StringBuilderfor the next row. - Iterate through each character of
currentRow. - If the character is '0', append "01" to the
StringBuilder. - If the character is '1', append "10" to the
StringBuilder. - After iterating, update
currentRowto the string from theStringBuilder. - After the main loop finishes,
currentRowholds the string for then-th row. - The result is the character at index
k-1. Convert the character '0' or '1' to an integer.
Walkthrough
The algorithm begins with the base case, row 1, which is simply "0". It then enters a loop that runs from row 2 to row n. In each iteration, it constructs the next row by scanning the current row. For every '0' encountered, it appends "01" to a new string builder, and for every '1', it appends "10". After the new row is fully constructed, it replaces the old row. This process continues until the n-th row is generated. Finally, it retrieves the character at the k-1-th index (since k is 1-indexed) and converts it to an integer to get the final answer.
class Solution { public int kthGrammar(int n, int k) { String currentRow = "0"; for (int i = 2; i <= n; i++) { StringBuilder nextRow = new StringBuilder(); // The length of the string can become very large, so we might not even // be able to build it for large n. This code is for demonstration. for (char c : currentRow.toCharArray()) { if (c == '0') { nextRow.append("01"); } else { nextRow.append("10"); } } currentRow = nextRow.toString(); } return currentRow.charAt(k - 1) - '0'; }}Complexity
Time
O(2^n). The length of the string for row `i` is `2^(i-1)`. Building the string for row `i` takes O(2^(i-1)) time. The total time is the sum of these lengths, which is dominated by the final step, resulting in O(2^n) complexity.
Space
O(2^n). We need to store the string for the `n`-th row, which has a length of `2^(n-1)`. This is infeasible for `n=30`.
Trade-offs
Pros
Simple to understand and directly follows the problem statement.
Cons
Highly inefficient for the given constraints (
n <= 30).Will result in Time Limit Exceeded (TLE) and Memory Limit Exceeded (MLE) on most platforms.
This approach leverages the self-similar structure of the grammar. We can observe that the n-th row is formed by taking the (n-1)-th row and appending its bitwise complement. This allows us to find the k-th symbol without constructing the full row by recursively determining its value from the previous row.
Algorithm
- Define a recursive function, say
solve(row, index). - Base Case: If
row == 1, the only symbol is 0. Return 0. - Calculate the length of the previous row,
prevRowLength = 2^(row - 2). - Recursive Step:
- If
indexis in the first half (i.e.,index <= prevRowLength), the symbol is the same as the symbol atindexin the previous row. We make a recursive call:solve(row - 1, index). - If
indexis in the second half (i.e.,index > prevRowLength), the symbol is the complement of the corresponding symbol in the previous row. The corresponding index in the previous row isindex - prevRowLength. We make a recursive callsolve(row - 1, index - prevRowLength)and return its complement (1 - result).
- If
Walkthrough
The key observation is that for any row n > 1, the first half of the row is identical to row n-1, and the second half is the bitwise complement (0s become 1s, 1s become 0s) of row n-1. The length of row n is 2^(n-1), so the midpoint is at index 2^(n-2). Based on this, we can determine the value of the k-th symbol. If k lies in the first half, its value is the same as the k-th symbol in row n-1. If k lies in the second half, its value is the complement of the (k - midpoint)-th symbol in row n-1. This logic forms a recursive relation that bottoms out at n=1, where the value is always 0.
class Solution { public int kthGrammar(int n, int k) { // Base case: The first row is just "0". if (n == 1) { return 0; } // Length of the previous row (n-1). int prevRowLength = 1 << (n - 2); // Equivalent to 2^(n-2) // If k is in the first half of the current row. if (k <= prevRowLength) { // The value is the same as in the previous row. return kthGrammar(n - 1, k); } else { // If k is in the second half, the value is the complement // of the corresponding element in the previous row. // The corresponding position is k - prevRowLength. return 1 - kthGrammar(n - 1, k - prevRowLength); } }}Complexity
Time
O(n). In each recursive call, `n` is decremented by 1. The recursion depth is `n`, and each call involves a constant number of operations.
Space
O(n). This is due to the recursion call stack depth, which can go up to `n`.
Trade-offs
Pros
Significantly more efficient than brute force and feasible for the given constraints.
The logic is intuitive once the fractal-like pattern is identified.
Cons
The recursive calls consume stack space, which could be a concern for extremely large
n(though not an issue withn <= 30).
This is the most optimal approach, derived from a deeper analysis of the recursive pattern. It connects the problem to the binary representation of k-1 and finds the answer in constant time. The value of the k-th symbol is simply the parity of the number of set bits in k-1.
Algorithm
- The problem asks for the
k-th symbol (1-indexed). We will work withk-1(0-indexed). - The core insight is that the value of the symbol at a given position is determined by the parity of the number of set bits in its 0-indexed position.
- Calculate
k-1. - Count the number of set bits (1s) in the binary representation of
k-1. Most languages provide a built-in function for this (e.g.,Integer.bitCount()in Java). - Find the parity of this count. If the count is even, the result is 0. If the count is odd, the result is 1. This is equivalent to
count % 2.
Walkthrough
Let's analyze the parent-child relationship using 0-indexed k. The k-th symbol in row n, S_n[k], is generated from the floor(k/2)-th symbol in row n-1. The generation rule 0 -> 01 and 1 -> 10 can be expressed as S_n[k] = S_{n-1}[floor(k/2)] XOR (k % 2). By expanding this recurrence relation down to the base case S_1[0] = 0, we find that S_n[k] is the XOR sum of all the bits in the binary representation of k. The XOR sum of bits is 1 if the number of set bits (popcount) is odd, and 0 if it is even. Therefore, for a 1-indexed k from the problem, the symbol is popcount(k-1) % 2.
class Solution { public int kthGrammar(int n, int k) { // The problem is equivalent to finding the parity of the number of set bits // in the binary representation of k-1. // If the count of 1s is even, the result is 0. // If the count of 1s is odd, the result is 1. // This is the same as Integer.bitCount(k - 1) % 2. return Integer.bitCount(k - 1) % 2; }}Complexity
Time
O(1). The `Integer.bitCount` operation is highly optimized and often translates to a single CPU instruction, making it effectively constant time for a fixed-size integer (like a 32-bit or 64-bit int).
Space
O(1). No extra space is used besides a few variables.
Trade-offs
Pros
Extremely efficient in both time and space.
The solution is very concise and elegant.
Cons
The underlying logic is less intuitive than the recursive approach and requires a mathematical insight into the pattern.
Solutions
Solution
class Solution {public int kthGrammar(int n, int k) { return Integer.bitCount(k - 1) & 1; }}class Solution {public: int kthGrammar(int n, int k) { return __builtin_popcount(k - 1) & 1; }};class Solution: def kthGrammar(self, n: int, k: int) -> int: return (k - 1). bit_count() & 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.