Kth Symbol in Grammar

Row 1 is 0. Build each next row by replacing every 0 with 01 and every 1 with 10, preserving order. Given a row number n and a one-based position k, return…

Row 1 is 0. Build each next row by replacing every 0 with 01 and every 1 with 10, preserving order. Given a row number n and a one-based position k, return the integer symbol at that position. Implement kth_symbol(n, k) in Python or kthSymbol(n, k) in the other languages. Do not construct or return the whole row.

- n and k are integers, not Booleans or fractional values. - 1 <= n <= 30 and 1 <= k <= 2^(n - 1). - Return the integer 0 or 1, not a string or Boolean. - Coding supports all 30 rows. Visualization shows complete journeys for rows 1 through 6.

Example 1: input n = 1, k = 1; output 0. The first row contains only 0.

Example 2: input n = 4, k = 4; output 0. Row 4 is 01101001; its fourth symbol is 0.

Example 3: input n = 4, k = 5; output 1. The first symbol in the second half of row 4 is 1.

Category: Recursion. Topic: recursion. Difficulty: Medium. Patterns: recursion, bit-manipulation.