## 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)]`.

## Rust Solution

``````struct Solution;

impl Solution {
fn kth_grammar(n: i32, k: i32) -> i32 {
let n = n as usize - 1;
let k = k as usize - 1;
Self::kth(n, k)
}
fn kth(n: usize, k: usize) -> i32 {
if n == 0 {
0
} else {
Self::kth(n - 1, k / 2) ^ (k % 2) as i32
}
}
}

#[test]
fn test() {
let n = 1;
let k = 1;
let res = 0;
assert_eq!(Solution::kth_grammar(n, k), res);
let n = 2;
let k = 1;
let res = 0;
assert_eq!(Solution::kth_grammar(n, k), res);
let n = 2;
let k = 2;
let res = 1;
assert_eq!(Solution::kth_grammar(n, k), res);
let n = 4;
let k = 5;
let res = 1;
assert_eq!(Solution::kth_grammar(n, k), res);
let n = 30;
let k = 417_219_134;
let res = 1;
assert_eq!(Solution::kth_grammar(n, k), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.