algoadvance

The problem is described as follows:

We build a table of n rows (1-indexed). We start with 0 in the 1st row. From the 2nd row onwards, every row is formed based on the previous row using the following rules:

• 0 becomes 01
• 1 becomes 10

Given two integers n and k, return the k-th (1-indexed) symbol in the n-th row of the table.

Clarifying Questions

1. Range of n: What is the maximum value for n? (This affects the computational feasibility)
2. Range of k: What is the maximum value for k?
3. Specific edge cases: Do we need to handle special edge cases such as n=1 or k=1?
4. Constraints: Are there any specific constraints we need to follow regarding space complexity?

Strategy

To solve this problem, we need to understand the relationship between the rows:

• The 1st row is 0.
• The 2nd row would be generated by replacing 0 in the 1st row, resulting in 01.
• The 3rd row would be generated by replacing every 0 with 01 and every 1 with 10 from the 2nd row, resulting in 0110, and so on.

Observations:

1. Each row effectively doubles the length of the previous row.
2. The first half of the row is generated in a different way compared to the second half.

Instead of generating the massive table, we can find a recursive pattern:

• The k-th symbol in nth row can be recursively considered as what the ceiling or floor index of (k+1)//2 in (n-1)th row would be.

The key insight is to identify the inverse process:

• If k is in the first half of the nth row, the answer will be the same as the (n-1)th row.
• If k is in the second half of the nth row, the answer will be the inverse of what it would have been in the (n-1)th row.

Code

Here is the Python code to solve the problem:

def kthGrammar(n: int, k: int) -> int:
    if n == 1:
        return 0
    if k % 2 == 0:
        return 1 - kthGrammar(n - 1, k // 2)
    else:
        return kthGrammar(n - 1, (k + 1) // 2)

# Example usage
print(kthGrammar(4, 5))  # Output: 1
print(kthGrammar(2, 2))  # Output: 1

Explanation

1. The base case is when n = 1, where the value is always 0.
2. For other cases, we determine if k is an even or odd number:
   • If k is even, we recursively call the function with k/2 in n-1 and invert the result.
   • If k is odd, we recursively call the function with (k+1)//2 in n-1.

Time Complexity

The time complexity is O(n) because we are making a single recursive call that goes all the way up to 1 recursively. Each call reduces n by 1, so the depth of the recursion is n, leading to a linear time complexity.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?