Problem 779

Abstract / Summary

Find the kth character in the nth row of a specific symbol generation grammar.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0779.py

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        # zero-based
        return (k - 1).bit_count() & 1
4 lines | 129 bytes | submitted October 26, 2023 | GitHub   33% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 49% (500k+ submissions).

Typical patterns to solve this problem:
  • Bit Manipulation
  • Math
  • Recursion
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a single method kthGrammar inside a Solution class. Its purpose is to compute the value of the k-th symbol in the n-th row of a specific binary grammar without constructing the entire grammar. The core logic reduces the problem to a parity calculation on the binary representation of k-1. By leveraging Python’s built-in bit_count method and a bitwise AND, the solution delivers the result in constant time and constant space.

Key Steps

The method consists of three conceptual steps: adjusting the index to zero-based, counting the set bits, and extracting the parity.

Adjusting to Zero-Based Index

The grammar definition is naturally one-based, but the parity trick works with zero-based positions. The code therefore subtracts one from k.

k_minus_one = k - 1

Counting Set Bits

Python’s integer method bit_count() returns the number of 1 bits in the binary representation of the argument. This count directly corresponds to the number of flips required to reach the target symbol when traversing from the root of the grammar tree.

ones = k_minus_one.bit_count()

Extracting Parity

The grammar’s rule dictates that each flip toggles the symbol between 0 and 1. Consequently, the final symbol is 1 if the number of flips is odd and 0 otherwise. The expression ones & 1 isolates the least-significant bit of the count, yielding the required parity.

result = ones & 1
return result

The complete method condenses these three steps into a single return statement:

return (k - 1).bit_count() & 1

Edge Cases Handled

When k equals 1, the subtraction yields 0. The binary representation of 0 contains no set bits, so bit_count() returns 0. The subsequent & 1 yields 0, which matches the first symbol of any row in the grammar. Similarly, for the smallest possible n (which is 1), the method still returns the correct value because the parity calculation does not depend on n. Large values of k are also accommodated because Python integers have arbitrary precision; the bit_count operation works correctly regardless of the magnitude of k.

Performance Optimizations

The implementation avoids any form of recursion, iteration, or explicit construction of the grammar rows. By translating the problem into a bit-parity query, it eliminates the exponential growth inherent in the grammar definition. The use of the built-in bit_count method is a hardware-aware operation that typically executes in a single CPU instruction on modern processors, providing a highly efficient count of set bits. The final bitwise AND is a trivial constant-time operation. As a result, the method executes in constant time with constant auxiliary memory, making it suitable for very large inputs.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a long game of telephone where the rules for what to say next are very special. Every row starts with a zero, and then it grows by turning every zero into a zero and a one, while every one turns into a one and a zero. If someone wants to know what number sits at a specific spot far down the line, this code finds the answer in a super fast way. It looks at the spot number and subtracts one because computers like to start counting from zero instead of one. After that, it counts how many ones are hiding inside the binary version of that number. If the count is an even number like two or four, the answer is zero. If the count is an odd number like one or three, the answer is one. It is like a clever shortcut for figuring out a pattern without needing to draw the whole thing out on a giant piece of paper.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 9 | μ = 8.26 | σ = 1.76

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java
leetcode.ca C++ Java Python Go TS
LeetcodeHelp C++ Java Python
Progiez C++ Java Python
github black-shadows C++
charles-wangkai Java
Dijkstra-Edu Java
everthis JS
fengvyi C++
JoshCrozier JS
lkwq007 Python
ruoru Rust
suxrobGM C#
varunu28 Java
wisdompeak Python
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Java
leetcode.ca C++, Go, Java, Python, TypeScript
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
Dijkstra-Edu Java
everthis JavaScript
fengvyi C++
JoshCrozier JavaScript
lkwq007 Python
ruoru Rust
suxrobGM C#
varunu28 Java
wisdompeak Python
zfang399 C++
29 links | 17 authors | 8 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

2 easy 4 medium
7 solutions   October 26, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality