We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

K-th Symbol in Grammar

Number: 795

Difficulty: Medium

Paid? No

Companies: Bloomberg, Amazon, DE Shaw, Google, Meta, Adobe, Uber

Problem Description

We build a table of n rows (1-indexed) starting with a single "0" in row 1. For each subsequent row, every occurrence of 0 is replaced with "01" and every occurrence of 1 with "10". Given integers n and k, return the kth (1-indexed) symbol in the nth row.

Key Insights

  • The kth symbol in the nth row is derived from a parent symbol in the previous row.
  • The parent’s position is determined by (k+1) // 2.
  • If k is odd, the kth symbol is identical to its parent; if even, the symbol is flipped.
  • Recursion helps trace back to the base case (row 1, symbol "0").

Space and Time Complexity

Time Complexity: O(n) - each recursive call does O(1) work with a maximum recursion depth of n. Space Complexity: O(n) - due to the recursion stack.

Solution

We use a recursive approach where for any kth symbol in the nth row, the parent symbol at row (n-1) is determined using the index (k+1)//2. If k is odd, the symbol remains the same as the parent's; if even, it is flipped (0 becomes 1 and vice versa). This process continues until the base case is reached at n = 1 where the symbol is always 0.

Code Solutions

# Python implementation for K-th Symbol in Grammar

def kthGrammar(n: int, k: int) -> int:
    # Base case: first row is always "0".
    if n == 1:
        return 0
    # Find the parent's position. The kth symbol's parent is at index (k+1)//2 in the previous row.
    parent = kthGrammar(n - 1, (k + 1) // 2)
    # If k is odd, the symbol is the same as the parent's; if even, return the flipped value.
    return parent if k % 2 == 1 else 1 - parent

# Sample test cases
if __name__ == "__main__":
    print(kthGrammar(1, 1))  # Expected output: 0
    print(kthGrammar(2, 1))  # Expected output: 0
    print(kthGrammar(2, 2))  # Expected output: 1
← Back to All Questions