Formatted question description: https://leetcode.ca/all/779.html

# 779. K-th Symbol in Grammar

## Level

Medium

## Description

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.)

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:**

`N`

will be an integer in the range`[1, 30]`

.`K`

will be an integer in the range`[1, 2^(N-1)]`

.

## Solution

Observe each row. It can be seen that row `N + 1`

is obtained from row `N`

by copying the content of row `N`

and then concatenating the reversed content of row `N`

. Row 1 is “0” and row 2 is “01”, which are quite obvious. For `N >= 2`

, the left half of the content in row `N`

and the right half of the content in row `N`

are reversed to each other, so the content of row `N + 1`

is obtained in the way mentioned above.

This problem can be solved without using `N`

, and only `K`

is needed. While `K`

is greater than 1, replace `K`

with its complement, where the complement of `K`

is defined as the smallest positive integer `C`

such that `K + C = 2^M + 1`

where `M`

is a positive integer.

Each time `K`

is replaced with its complement, does the symbol change? Calculate `log = Math.ceil(Math.log(K) / Math.log(2))`

. If `log`

is odd, then the symbol changes. Otherwise, the symbol remains unchanged.

After `K`

becomes 1, count the number of times that the symbol is changed. Since the symbol at index 1 is 0, if the symbol is changed odd number of times, return 1. Otherwise, return 0.

```
class Solution {
public int kthGrammar(int N, int K) {
int reverseCount = 0;
while (K > 1) {
int log = (int) Math.ceil(Math.log(K) / Math.log(2));
int power2 = (int) Math.pow(2, log);
K = power2 + 1 - K;
if (log % 2 == 1)
reverseCount++;
}
return reverseCount % 2;
}
}
```