Is K-th Symbol in Grammar easy or hard?

K-th Symbol in Grammar is generally considered a medium difficulty problem. The challenge comes from recognizing that you should not build the entire row, which would be exponential. Once you see the parent relationship and flip rule, the recursive or iterative solution becomes straightforward.

How to solve K-th Symbol in Grammar in O(n)?

Start from position k in row n and repeatedly move to its parent position (k+1)/2 in the previous row. If k is even, the value flips relative to the parent; if k is odd, it remains the same. Continue until reaching row 1 which contains 0, then apply the accumulated flips. This takes O(n) steps and constant extra space in the iterative version.

What is the best approach for K-th Symbol in Grammar?

The most common approach is recursive parent tracking. Each position in row n comes from a parent in row n-1, and even indices flip the parent value while odd indices keep it. This gives an O(n) time solution with O(n) recursion stack space. Many optimized implementations convert the same logic into an iterative O(1) space solution.

Is K-th Symbol in Grammar asked at Google/Amazon/Meta?

K-th Symbol in Grammar appears in interview preparation sets for major tech companies including Google, Amazon, and Meta. It tests recursion reasoning, binary tree style parent relationships, and bit manipulation insights, making it a common medium-level interview problem.

What data structure is used in K-th Symbol in Grammar?

The problem does not require building the full grammar string or using a complex data structure. Most solutions rely on recursion or iterative computation with simple integer operations. Conceptually, the grammar forms a binary tree structure where each node derives from a parent.

What is the time complexity of K-th Symbol in Grammar?

The typical recursive or iterative solution runs in O(n) time because you move from row n to row 1 step by step while determining the parent index. Space complexity is O(n) with recursion due to the call stack, or O(1) when implemented iteratively.

K-th Symbol in Grammar Python or Java solution approach?

Python and Java implementations usually follow the same logic: either a recursive function that calls k-th symbol for the parent index, or an iterative loop that tracks flips while reducing k to its parent. Both run in O(n) time and avoid constructing the exponentially large rows.

Description Hints 1 Solution Video 23:32

779. K-th Symbol in Grammar

Medium48.7% acceptance7 companies

We build a table of n rows (1-indexed). We start by writing 0 in the 1^st 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 1^st row is 0, the 2^nd row is 01, and the 3^rd row is 0110.

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

Example 1:

Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0

Example 2:

Input: n = 2, k = 1
Output: 0
Explanation: 
row 1: 0
row 2: 01

Example 3:

Input: n = 2, k = 2
Output: 1
Explanation: 
row 1: 0
row 2: 01

Constraints:

1 <= n <= 30
1 <= k <= 2^{n - 1}

Asked at 7 companies

D. E. Shaw Microsoft

Google Goldman Sachs Amazon Meta Bloomberg

Topics

Hints open one at a time

Hint 1

Try to represent the current (N, K) in terms of some (N-1, prevK). What is prevK ?

23:32

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def kthGrammar(self, n: int, k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

1
1

Input

2
1

Input

2
2

Your code is saved on this device.Solution