# 0779. K-th Symbol in Grammar
###### tags: `Leetcode` `Medium` `Math` `Recursion`
Link: https://leetcode.com/problems/k-th-symbol-in-grammar/description/
## 思路
### Recursion $O(n)$
### Bit Manipulation $O(1)$
思路参考[这里](https://leetcode.com/problems/k-th-symbol-in-grammar/solutions/113705/java-one-line/?orderBy=most_votes)

**Observation 1**: let ```f(k)``` be the value of ```k```th position (0-based), then:

f(2 * k) = 0 {if f(k) = 0} or, 1 {if f(k) = 1} => f(2 * k) = f(k) xor 0
f(2 * k + 1) = 0 {if f(k) = 1} or 1 {if f(k) = 0} => f(2 * k + 1) = f(k) xor 1

**Observation 2**: if binary string of ```k``` is used, let ```k = 1001010```, then we have:

f(1001010) = f(100101) ^ 0 = f(10010) ^ 1 ^ 0 = f(1001) ^ 0 ^ 1 ^ 0 = ... = f(0) ^ 1 ^ 0 ^ 0 ^1 ^ 0 ^ 1 ^ 0 = 1 ^ 0 ^ 0 ^1 ^ 0 ^ 1 ^ 0

So, the result is the xor operation on all bits of ```k```. Since 0 does not change xor result, we can ignore all 0s.

f(1001010) = 1 ^ 1 ^ 1 = (1^1) ^ 1 = 0 ^ 1 = 1
f(11110011) = 1 ^ 1^ 1 ^ 1 ^ 1 ^1 = (1 ^ 1) ^ (1 ^ 1) ^ (1 ^1) = 0

Now, it's easy to tell ```f(k) = 0``` if ```k``` has even number of 1s in binary representation, and ```f(k) = 1``` when ```k``` has odd number of 1s
## Code
Recursion

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n==1 and k==1: return 0
        prev = self.kthGrammar(n-1, (k+1)//2)
        if prev==0:
            return 0 if k%2==1 else 1
        else:
            return 1 if k%2==1 else 0

Bit Manipulation

class Solution {
    public int kthGrammar(int n, int k) {
        return Integer.bitCount(k-1)&1;
    }
}