Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 779 with 14 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 779 # by problem number
lcpy gen -s kth_symbol_in_grammar # by problem name
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.
n = 3, the 1st row is 0, the 2nd row is 01, and the 3rd row is 0110.n and k, return the kth (1-indexed) symbol in the nth row of a table of n rows.
Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0
Input: n = 2, k = 1
Output: 0
Explanation:
row 1: 0
row 2: 01
Input: n = 2, k = 2
Output: 1
Explanation:
row 1: 0
row 2: 01
class Solution:
# Time: O(1)
# Space: O(1)
def kth_grammar(self, n: int, k: int) -> int:
# kth symbol = parity of set bits in k - 1
return (k - 1).bit_count() % 2
| Time | Space |
|---|---|
| O(1) | O(1) |