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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

K-th Symbol in Grammar

Difficulty: Medium

Problem Description

We build a table of 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. Given two integer n and k, return the k-th (1-indexed) symbol in the n-th row of a table of n rows.

Key Insights

  • The sequence is generated by recursively replacing symbols based on their previous row.
  • Each row doubles the length of the previous row, leading to a total of 2^(n-1) symbols in the n-th row.
  • The k-th symbol can be determined without building the entire row by utilizing the properties of binary representation.

Space and Time Complexity

Time Complexity: O(n) - The solution involves finding the k-th symbol through recursive steps based on the binary representation of k. Space Complexity: O(1) - Only a constant amount of space is used for variables during computation.

Solution

To find the k-th symbol in the n-th row of the sequence, we can utilize recursive properties. The k-th symbol can be determined based on the parent symbol's position in the previous row. If k is odd, the symbol is the same as the parent; if k is even, the symbol is the opposite. This can be computed efficiently without generating the entire row.

Code Solutions

def kthSymbol(n: int, k: int) -> int:
    if n == 1:
        return 0  # Base case: first row only contains '0'
    
    # Determine parent position: (k + 1) // 2
    parent_k = (k + 1) // 2
    parent_symbol = kthSymbol(n - 1, parent_k)  # Recursive call to find the parent symbol
    
    # If k is even, return the opposite of the parent symbol
    return parent_symbol ^ 1 if k % 2 == 0 else parent_symbol
← Back to All Questions