Solution Explanation for 779. K-th Symbol in Grammar

This problem asks to find the k-th symbol in the n-th row of a grammar where each row is generated from the previous row by replacing 0 with 01 and 1 with 10. Two approaches are presented below.

Approach 1: Recursive Approach

This approach directly implements the grammar's generation rule recursively.

Logic:

1. Base Case: If n is 1 (first row), the only symbol is 0, so return 0.

2. Recursive Step:

   • If k is less than or equal to half the length of the current row (2n-2), the k-th symbol in the current row is the same as the k-th symbol in the previous row. Recursively call the function with n-1 and k.
   • Otherwise, the k-th symbol in the current row is the opposite of the (k - 2n-2)-th symbol in the previous row. Recursively call the function with n-1 and k - 2<sup>n-2</sup>, and XOR the result with 1.

Code (Python):

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1:
            return 0
        if k <= (1 << (n - 2)):
            return self.kthGrammar(n - 1, k)
        return self.kthGrammar(n - 1, k - (1 << (n - 2))) ^ 1
 

Time Complexity: O(n) - The recursion depth is at most n.

Space Complexity: O(n) - Due to the recursive call stack.

Approach 2: Bit Manipulation Approach

This approach leverages the observation that the k-th symbol is determined by the number of 1s in the binary representation of k-1.

Logic:

The grammar generates a sequence where the number of 1s in the binary representation of the index (k-1) determines whether the symbol is 0 or 1. An odd number of 1s means the symbol is 1; an even number means it's 0. This can be efficiently checked using bit counting.

Code (Python):

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        return (k - 1).bit_count() & 1

Time Complexity: O(log k) - The bit_count() operation (or its equivalent in other languages) takes logarithmic time relative to the input k.

Space Complexity: O(1) - Constant extra space is used.

Comparison:

The bit manipulation approach (Approach 2) is significantly more efficient than the recursive approach (Approach 1), especially for larger values of n and k. The recursive approach has a time complexity that grows linearly with n, while the bit manipulation approach has a logarithmic time complexity. The space complexity also improves from O(n) to O(1). Therefore, Approach 2 is the preferred solution.

The code in other languages (Java, C++, Go) follows the same logic as the Python code for both approaches, using their respective bit manipulation functions (e.g., Integer.bitCount() in Java, __builtin_popcount() in C++, bits.OnesCount() in Go).