# 779. 第 K 个语法符号

我们构建了一个包含 n 行 ( 索引从 1  开始 ) 的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的 0 替换为 01，1 替换为 10。

• 例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第 3 行是 0110 。

给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）

示例 1:

输入: n = 1, k = 1
输出: 0
解释: 第一行：0

示例 2:

输入: n = 2, k = 1
输出: 0
解释: 
第一行: 0 
第二行: 01

示例 3:

输入: n = 2, k = 2
输出: 1
解释:
第一行: 0
第二行: 01

提示:

• 1 <= n <= 30
• 1 <= k <= $2^n - 1$

# 题解

这道题和腾讯笔试题很像。
本质上每一次操作都是在上一行基础上添加其按位取反后的结果。

class Solution {
public:
    int kthGrammar(int n, int k) {
        k--;
        int res = 0;
        while (k > 0) {
            k &= k - 1;
            res ^= 1;
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：$O (logk)$
• 空间复杂度：$O (1)$