K-th Symbol in Grammar - Practice Coding Problems

K-th Symbol in Grammar - Problem

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, the 1st row is 0, the 2nd row is 01, and the 3rd row is 0110.

Given two integers n and k, return the k-th (1-indexed) symbol in the n-th row of a table of n rows.

Input & Output

Example 1 — Basic Case

$ Input: n = 1, k = 1

› Output: 0

💡 Note: Row 1 contains only "0", so the 1st symbol is 0

Example 2 — Second Row

$ Input: n = 2, k = 1

› Output: 0

💡 Note: Row 2 is "01" (from "0" → "01"), so the 1st symbol is 0

Example 3 — Fourth Row

$ Input: n = 4, k = 5

› Output: 1

💡 Note: Row 4 is "01101001" (0→01, 1→10, 1→10, 0→01), so the 5th symbol is 1

Constraints

1 ≤ n ≤ 30
1 ≤ k ≤ 2^n-1

Visualization

Tap to expand

Understanding the Visualization

Input

Given row number n and position k

Process

Build grammar table using 0→01, 1→10 rule

Output

Return the k-th symbol in row n

Key Takeaway

🎯 Key Insight: The grammar forms a binary tree where each node's children follow the pattern 0→(0,1) and 1→(1,0)

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is recognizing that the grammar table forms a binary tree structure where each position's value depends on its parent. The most efficient approach uses recursion with parent-child relationships - find the parent position in the previous row and apply the transformation rule based on whether the current position is a left or right child. Time: O(n), Space: O(n) due to recursion depth.

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Pattern	O(n)	O(1)	Use binary tree structure and bit manipulation to find the answer directly
Build Complete Rows	O(2ⁿ)	O(2ⁿ)	Generate each row completely until reaching row n
Bit Manipulation	O(log k)	O(1)	Count the number of 1s in binary representation of (k-1) to determine the result

Mathematical Pattern — Algorithm Steps

Recognize that row n has 2^(n-1) elements forming a binary tree
Use (k-1) in binary to determine the path from root to target position
Traverse path: 0 bit means left child (keep value), 1 bit means right child (flip value)
Start with root value 0 and apply transformations based on path

Visualization

Tap to expand

Step-by-Step Walkthrough

Tree Structure

Each row forms a binary tree level

Parent-Child

Find parent position and determine left/right child

Result

Apply transformation rule based on child position

Code -

solution.c — C

#include <stdio.h>

int solution(int n, int k) {
    if (n == 1) {
        return 0;
    }
    
    // Find the parent's value in the previous row
    int parentPos = (k + 1) / 2;
    int parentVal = solution(n - 1, parentPos);
    
    // If k is odd (left child), return parent value
    // If k is even (right child), return flipped parent value
    if (k % 2 == 1) {
        return parentVal;
    } else {
        return 1 - parentVal;
    }
}

int main() {
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    printf("%d\n", solution(n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

We process at most n bits to determine the path from root to target position

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track current position and result

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Pattern — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler