# 779. K-th Symbol in Grammar

On the first row, we write a 0. 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.

Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).

`Examples: Input: N = 1, K = 1 Output: 0 Input: N = 2, K = 1 Output: 0 Input: N = 2, K = 2 Output: 1 Input: N = 4, K = 5 Output: 1 Explanation: row 1: 0 row 2: 01 row 3: 0110 row 4: 01101001  Note:`1. N` will be an integer in the range `[1, 30]`.`2. K` will be an integer in the range `[1, 2^(N-1)]`.  `

# My Solution(36ms 12.8MB)

``````public class Solution {
public int KthGrammar(int N, int K) {
return recursiveFind(K - 1);
}

private int recursiveFind(int k)
{
if (k == 0)
{
return 0;
}
else if (k % 2 == 1)
{
return inverse(recursiveFind(k / 2));
}
else
{
return recursiveFind(k / 2);
}
}

private int inverse(int k)
{
return k == 1 ? 0 : 1;
}
}``````

# No.1 Solution(36ms)

``````public class Solution {
public int KthGrammar(int N, int K) {
return helper(N, K-1);
}

public int helper(int N,int K) {
if(N==1||K==0) return 0;
else {
if(K%2==0) return helper(N-1,K/2);
else return helper(N-1,K/2) ^ 1;
}
}
}``````

# Things to improve

There is not much things to improve in this case, it’s recursive logic and I personally don’t like recursive…