779. K-th Symbol in Grammar - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

We build rows of a special grammar on a 1‑indexed basis:

Row 1 is "0".
To get row i from row i−1, replace every 0 with "01" and every 1 with "10".
Given two integers n and k, return the kᵗʰ symbol (0 or 1) in row n.

Examples

Example 1

Input  n = 1, k = 1  
Output 0  
Explanation  Row 1 = "0". The 1ˢᵗ symbol is 0.

Example 2

Input  n = 2, k = 1  
Output 0  
Explanation  Row 2 = "01". The 1ˢᵗ symbol is 0.

Example 3

Input  n = 2, k = 2  
Output 1  
Explanation  Row 2 = "01". The 2ⁿᵈ symbol is 1.

Constraints

1 ≤ n ≤ 30
1 ≤ k ≤ 2ⁿ⁻¹

Hints

Can you avoid building the entire row string of length 2ⁿ⁻¹ by seeing how a single symbol maps back to the previous row?
If you know the kᵗʰ symbol in row n comes from position p in row n−1, how does its value relate to that of row n−1?
Are there bit‑tricks or parity observations that give you the answer directly for a given k?

Approach 1 – Brute‑Force Generation

Idea

Actually build each row from 1 up to n by repeatedly applying the replacement rules, then index into the final string.

Steps

Start with s = "0".
Repeat n−1 times:
- Build t = "".
- For each character c in s, append "01" if c=='0', else "10".
- Set s = t.
Return s.charAt(k−1).

Code (Python)

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time: O(2ⁿ) string growth → exponential, impractical for n=30.
Space: O(2ⁿ) to hold the final string.

Approach 2 – Recursive Back‑Tracing (O(n))

Idea

A symbol in row n at position k either came from a 0 or 1 in row n−1 at position

p = (k+1)//2

—if k is odd, it’s the first child of that parent (same bit); if k even, it’s the second child (flipped bit).

Recurrence:

f(1,1) = 0  
if k is odd:   f(n,k) = f(n−1, (k+1)//2)  
else (k even): f(n,k) = 1 − f(n−1, (k+1)//2)

Steps

Base: if n==1 and k==1, return 0.
Compute parent index p = (k+1)//2.
Recursively get parent = f(n−1, p).
If k even, return 1−parent; else return parent.

Code (Python)

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time: O(n) recursion depth ≤30.
Space: O(n) call stack.

Approach 3 – Bit‑Parity Trick (O(1))

Idea

It can be shown that the kᵗʰ symbol equals the parity of the number of 1‑bits in (k−1). Specifically:

answer = popcount(k−1) % 2

Because each step “flips” the bit when you go to an even child, you accumulate one flip per 1‑bit in k−1.

Code (Python)

Python3

. . . .

Code (Java)

Java

. . . .

Complexity Analysis

Time: O(1) bit operations.
Space: O(1).

Step‑by‑Step Walkthrough (n=4, k=5)

Row 4 = "01101001". We want the 5ᵗʰ symbol:

Brute‑force builds all rows then indexes → gets '1'.
Recursive:
1. f(4,5) → parent = f(3,3) since (5+1)//2=3, k even → return 1−f(3,3).
2. f(3,3) → parent = f(2,2), k odd → return f(2,2).
3. f(2,2) → parent = f(1,1), k even → return 1−f(1,1) = 1.
4. Back up: f(3,3)=1, f(4,5)=1−1=0? (Oops, our parity says 1—check step: for f(4,5), k=5 odd, so it should return parent directly. Indeed k=5 is odd, so f(4,5)=f(3,3)=1.)
Bit‑parity: k−1=4→binary 100 has one 1-bit→1.

Common Mistakes

Off‑by‑one mixing 0‑based vs 1‑based indexing of k.
Forgetting to flip when k is even.
Using brute force for n up to 30 → may TLE or OOM in some languages.

Edge Cases

n=1,k=1 → always 0.
Largest n=30, k=2²⁹ → recursion safe, bit trick instant.
k out of range (not in problem domain).

Alternative Variations

Different replacement rules (e.g. 0→“0 1 0”, 1→“1 0 1”).
Multi‑symbol grammars that branch into more than two.

Pow(x, n) – fast exponentiation pattern.
Number Complement – bitwise flipping.

779. K-th Symbol in Grammar - Detailed Explanation

Problem Statement

Examples

Constraints

Hints

Approach 1 – Brute‑Force Generation

Idea

Steps

Code (Python)

Java Code

Complexity Analysis

Approach 2 – Recursive Back‑Tracing (O(n))

Idea

Steps

Code (Python)

Java Code

Complexity Analysis

Approach 3 – Bit‑Parity Trick (O(1))

Idea

Code (Python)

Code (Java)

Complexity Analysis

Step‑by‑Step Walkthrough (n=4, k=5)

Common Mistakes

Edge Cases

Alternative Variations

Related Problems