Package g0701_0800.s0779_k_th_symbol_in_grammar

Class Solution

java.lang.Object

g0701_0800.s0779_k_th_symbol_in_grammar.Solution

public class Solution
extends Object

779 - K-th Symbol in Grammar.<p>Medium</p> <p>We build a table of <code>n</code> rows ( <strong>1-indexed</strong> ). We start by writing <code>0</code> in the <code>1^st</code> row. Now in every subsequent row, we look at the previous row and replace each occurrence of <code>0</code> with <code>01</code>, and each occurrence of <code>1</code> with <code>10</code>.</p> <ul> <li>For example, for <code>n = 3</code>, the <code>1^st</code> row is <code>0</code>, the <code>2^nd</code> row is <code>01</code>, and the <code>3^rd</code> row is <code>0110</code>.</li> </ul> <p>Given two integer <code>n</code> and <code>k</code>, return the <code>k^th</code> ( <strong>1-indexed</strong> ) symbol in the <code>n^th</code> row of a table of <code>n</code> rows.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> n = 1, k = 1</p> <p><strong>Output:</strong> 0</p> <p><strong>Explanation:</strong> row 1: 0</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> n = 2, k = 1</p> <p><strong>Output:</strong> 0</p> <p><strong>Explanation:</strong> row 1: 0 row 2: 01</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> n = 2, k = 2</p> <p><strong>Output:</strong> 1</p> <p><strong>Explanation:</strong> row 1: 0 row 2: 01</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= n <= 30</code></li> <li><code>1 <= k <= 2^{n - 1}</code></li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	kthGrammar(int n, int k)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

kthGrammar

public int kthGrammar(int n,
 int k)