779. K-th Symbol in Grammar LeetCode Solution

In this guide, you will get 779. K-th Symbol in Grammar LeetCode Solution with the best time and space complexity. The solution to K-th Symbol in Grammar problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. K-th Symbol in Grammar solution in C++
4. K-th Symbol in Grammar solution in Java
5. K-th Symbol in Grammar solution in Python
6. Additional Resources

Problem Statement of K-th Symbol in Grammar

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.

For example, for n = 3, the 1st row is 0, the 2nd row is 01, and the 3rd row is 0110.

Given two integer n and k, return the kth (1-indexed) symbol in the nth row of a table of n rows.

Example 1:

Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0

Example 2:

Input: n = 2, k = 1
Output: 0
Explanation:
row 1: 0
row 2: 01

Example 3:

Input: n = 2, k = 2
Output: 1
Explanation:
row 1: 0
row 2: 01

Constraints:

1 <= n <= 30
1 <= k <= 2n – 1

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

779. K-th Symbol in Grammar LeetCode Solution in C++

class Solution {
 public:
  int kthGrammar(int n, int k) {
    if (n == 1)
      return 0;
    if (k % 2 == 1)
      return kthGrammar(n - 1, (k + 1) / 2) != 0;  // the left node
    return kthGrammar(n - 1, k / 2) == 0;          // the right node
  }
};
/* code provided by PROGIEZ */

779. K-th Symbol in Grammar LeetCode Solution in Java

class Solution {
  public int kthGrammar(int n, int k) {
    if (n == 1)
      return 0;
    if (k % 2 == 1)
      return kthGrammar(n - 1, (k + 1) / 2) == 0 ? 0 : 1; // the left node
    return kthGrammar(n - 1, k / 2) == 0 ? 1 : 0;         // the right node
  }
}
// code provided by PROGIEZ

779. K-th Symbol in Grammar LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.