LeetCode 779 - K-th Symbol in Grammar

LeetCode Problem 779

Difficulty: 🟡 Medium
Topics: Math, Bit Manipulation, Recursion

Solution

Problem Understanding

The problem defines a special binary grammar sequence that grows row by row. The first row contains only a single value:

0

Every later row is generated from the previous one using these rules:

• Replace every 0 with 01
• Replace every 1 with 10

This means the rows evolve like this:

Row 1: 0
Row 2: 01
Row 3: 0110
Row 4: 01101001

We are given two integers:

• n, the row number, using 1-based indexing
• k, the position inside that row, also using 1-based indexing

The task is to return the value at position k in row n.

The constraints are relatively small:

• 1 <= n <= 30
• 1 <= k <= 2^n - 1

The important detail is that the row size doubles every time. Row n contains 2^(n-1) elements. Even though n is only up to 30, directly constructing the rows becomes inefficient because the final row could contain hundreds of millions of characters.

A naive implementation that explicitly builds the strings would consume too much memory and time for larger values of n.

Several edge cases are important:

• n = 1, k = 1, the smallest possible input
• Positions near the middle of the row, because the recursive structure changes there
• Large values of n, where brute force construction becomes infeasible
• Cases where k refers to a symbol generated from a flipped parent value

The problem guarantees that k is always valid for the given row, so we never need to handle out-of-bounds indices.

Approaches

Brute Force Approach

The most direct solution is to literally generate each row from the previous row.

We start with:

0

Then repeatedly apply the transformation rules:

• 0 -> 01
• 1 -> 10

For example:

0
01
0110
01101001

After generating row n, we return the (k - 1)th character.

This approach is correct because it follows the exact process described in the problem statement. However, it quickly becomes inefficient because each row doubles in size.

The length of row n is:

2^(n - 1)

For n = 30, this is over 500 million characters, which is far too large to construct explicitly.

Optimal Approach

The key observation is that every symbol comes from a parent symbol in the previous row.

Each symbol generates exactly two children:

Parent	Children
0	0 1
1	1 0

Notice an important pattern:

• The left child is always the same as the parent
• The right child is always the opposite of the parent

This allows us to trace any position backward toward row 1.

If we know whether the current position is a left child or right child, we can determine whether the value changes.

Another important insight is that the answer depends on how many flips occur while tracing back to the root 0.

A very elegant mathematical observation emerges:

• Every time we move to a right child, the bit flips
• The number of flips equals the number of 1 bits in (k - 1)
• If the number of set bits is even, the result is 0
• If the number of set bits is odd, the result is 1

This produces an extremely efficient solution using bit manipulation.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(2^n)	Explicitly builds every row
Optimal	O(log k)	O(1)	Counts bit flips using bit manipulation

Algorithm Walkthrough

Optimal Bit Manipulation Algorithm

1. Observe that the first symbol is always 0.

Every later symbol is produced by a sequence of flips from this original value. 2. Convert the position into zero-based indexing.

Instead of working with k, work with k - 1.

This aligns naturally with binary representations and parent-child relationships. 3. Count the number of set bits in (k - 1).

Each set bit corresponds to moving into a right child during traversal.

A right child flips the value. 4. Determine whether the number of flips is even or odd.

• Even number of flips means the value remains 0
• Odd number of flips means the value becomes 1

5. Return the parity of the set bit count.

In code:

return bin(k - 1).count("1") % 2

Why it works

The grammar forms a binary tree structure where:

• Left child preserves the parent's value
• Right child flips the parent's value

The binary representation of (k - 1) encodes the path from the root to the target position. Every 1 bit represents taking a right branch, which flips the symbol once.

Therefore, the final value depends entirely on whether the number of right moves is even or odd.

Python Solution

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        return bin(k - 1).count("1") % 2

The implementation is intentionally concise because the mathematical observation completely eliminates the need for recursion or simulation.

The expression k - 1 converts the position into zero-based indexing, which aligns naturally with binary traversal logic.

bin(k - 1) converts the number into a binary string.

.count("1") counts how many set bits exist. Each set bit represents one flip in the grammar generation process.

Finally, % 2 determines whether the number of flips is odd or even.

• Even flips produce 0
• Odd flips produce 1

The parameter n is not directly used because the value at position k depends only on the flip pattern encoded in k - 1. The constraints guarantee that k is valid for row n.

Go Solution

func kthGrammar(n int, k int) int {
    k--

    count := 0

    for k > 0 {
        count += k & 1
        k >>= 1
    }

    return count % 2
}

The Go implementation manually counts set bits using bitwise operations instead of converting to a binary string.

The expression k & 1 checks whether the least significant bit is set.

k >>= 1 shifts the number right by one bit to continue processing.

This approach avoids string allocation and remains fully constant-space.

Go integers are easily sufficient for the problem constraints because the maximum value involved is well within 32-bit integer range.

Worked Examples

Example 1

Input: n = 1, k = 1

We compute:

Step	Value
k - 1	0
Binary	0
Number of set bits	0
Parity	Even
Result	0

Final answer:

0

Example 2

Input: n = 2, k = 1

Row 2 is:

01

Now trace the algorithm:

Step	Value
k - 1	0
Binary	0
Number of set bits	0
Parity	Even
Result	0

Final answer:

0

Example 3

Input: n = 2, k = 2

Row 2 is:

01

Now trace the algorithm:

Step	Value
k - 1	1
Binary	1
Number of set bits	1
Parity	Odd
Result	1

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log k)	We process each bit of k once
Space	O(1)	Only a few variables are used

The algorithm examines the binary representation of k - 1. A number with value k contains at most log₂(k) bits, so the runtime is logarithmic.

The solution uses constant extra memory because no recursion stack, arrays, or constructed rows are required.

Test Cases

solution = Solution()

assert solution.kthGrammar(1, 1) == 0  # Smallest possible input

assert solution.kthGrammar(2, 1) == 0  # First element of second row
assert solution.kthGrammar(2, 2) == 1  # Second element of second row

assert solution.kthGrammar(3, 1) == 0  # Beginning of row
assert solution.kthGrammar(3, 2) == 1  # Flip occurs
assert solution.kthGrammar(3, 3) == 1  # Consecutive ones
assert solution.kthGrammar(3, 4) == 0  # End of row

assert solution.kthGrammar(4, 5) == 1  # Middle position
assert solution.kthGrammar(4, 8) == 1  # Last position in row

assert solution.kthGrammar(5, 16) == 0  # Power-of-two boundary

assert solution.kthGrammar(10, 512) == 1  # Large row, valid position

assert solution.kthGrammar(30, 1) == 0  # Large n, smallest k
assert solution.kthGrammar(30, 536870912) == 1  # Largest valid position

Test Case Summary

Test	Why
(1, 1)	Minimum input size
(2, 1)	Left child preserves value
(2, 2)	Right child flips value
(3, 4)	End of small row
(4, 5)	Middle position traversal
(5, 16)	Power-of-two boundary
(10, 512)	Larger input validation
(30, 1)	Maximum row with smallest position
(30, 536870912)	Largest valid position

Edge Cases

Smallest Possible Input

The smallest valid input is:

n = 1, k = 1

This case is important because there is no parent row to recurse into. Many recursive implementations fail if the base case is not handled correctly.

Our implementation naturally handles this because:

k - 1 = 0

The number of set bits is zero, so the result is correctly 0.

Largest Valid Position

The largest possible valid position occurs near:

n = 30
k = 2^(29)

A brute-force solution would attempt to build enormous strings, which would consume excessive memory and time.

The optimal solution never constructs the rows. It only examines the bits of k, so performance remains efficient even for the maximum constraints.

Positions Generated by Multiple Flips

Some positions involve several right-child traversals, causing multiple flips.

For example:

k = 8
k - 1 = 7
binary = 111

There are three set bits, meaning three flips:

0 -> 1 -> 0 -> 1

An incorrect implementation might only consider the most recent flip instead of the total parity of flips.

Our implementation correctly counts all set bits and computes the parity, guaranteeing the correct final value.