algoadvance

Leetcode 779. K

Problem Statement

The K-th Symbol in Grammar problem can be formulated as follows:

We build a table of n rows (1-indexed). We start by writing “0” in the 1st row. Then, 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 integers n and k, return the k-th indexed symbol in row n. (The values of k are 1-indexed.)

Examples:

1. Input: n = 1, k = 1 Output: 0

2. Input: n = 2, k = 1 Output: 0

3. Input: n = 2, k = 2 Output: 1

Constraints:

• 1 <= n <= 30
• 1 <= k <= 2^(n-1)

Clarifying Questions

1. What should be returned if the inputs are invalid (such as k > 2^(n-1))?
   • Constraints ensure k is valid.
2. Should the problem be solved recursively or iteratively?
   • It can be solved using either method, but recursive is more straightforward due to the nature of the problem.

Strategy

To solve the problem, observe the properties of the sequence:

• The sequence grows as described, transforming “0” to “01” and “1” to “10”.
• This problem can be solved using a recursive approach.

Key Observations:

1. Determine the parent of k in the previous row:
   • Symbol at index k in row n depends on the symbol at index ceil(k / 2) in row n-1.
2. Define recursively based on the parent’s value:
   • If k is odd, it can either be “0” or “1”.
   • If k is even, it can either be “1” or “0”.

Code

public class KthSymbolInGrammar {
    public int kthGrammar(int n, int k) {
        if (n == 1) {
            return 0;  // Base case: The first row is always "0"
        }
        
        int parent = kthGrammar(n - 1, (k + 1) / 2);  // Recursively find the parent symbol
        boolean isKEven = k % 2 == 0;

        // If parent is 0: "0" -> "01", If parent is 1: "1" -> "10"
        if (parent == 0) {
            return isKEven ? 1 : 0;
        } else {
            return isKEven ? 0 : 1;
        }
    }
    
    public static void main(String[] args) {
        KthSymbolInGrammar solver = new KthSymbolInGrammar();
        System.out.println(solver.kthGrammar(1, 1));  // Output: 0
        System.out.println(solver.kthGrammar(2, 1));  // Output: 0
        System.out.println(solver.kthGrammar(2, 2));  // Output: 1
        // Further testing can be done here
    }
}

Time Complexity

The time complexity of this recursive solution can be analyzed as:

• Each recursive call reduces the problem size by 1, reaching from n to 1.
• Therefore, the number of recursive calls is n.

Thus, the time complexity is:

[ O(n) ]

This solution is efficient given the constraints (1 <= n <= 30).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?