# LeetCode Medium 779. K-th Symbol in Grammar

tags: leetcode

問題

• Explore
• Problems

最初の行では0と書く.そして,全ての次の行で前の行の0を01と置き換え, 1を10と置き換える.

行NとindexKが与えられた時, 行NのK番目の記号を返せ.(indexは$1$から始まる)

注意:

1. $N \in [1, 30], N \in \mathbb{N}$

2. $K \in [1, 2^{N-1}], K \in \mathbb{N}$

解法1(recursive)

まずは基底を考えます

初め, 0であり, 0は01となります. そのため1番目の数はいつでも0であり, 2番目の数は常に1です.よって

• $K=1$のときは$0$を返す
• $K=2$のときは$1$を返す

というのが基底です

次に再帰的な構造について考えます

次の行に行くと0は01, 1は10になり, 数字の総数は倍になります.

上のように数字が生成されますが, このとき0と1は2つのパターンでしか生成されないことに注目します

生成パターン

• 0は0から生成される2文字の1文字目, もしくは1から生成される2文字の2文字目のどちらかからしか生成されません
• 1は1から生成される2文字の1文字目, もしくは1から生成される2文字の2文字目のどちらかからしか生成されません
• また, 0, 1から生成されるのは毎回2文字なので奇数番目にある文字は生成された2文字の1文字目です.偶数番目にある文字は生成された2文字の2番目です

$i$番目までの数から$2i$文字が生成されます. そのため, $K$が偶数なら前の行の$K/2$番目の文字から生成された文字の2番目の文字ということになります

$K$が奇数なら前の行の$(K - 1) / 2 + 1$番目も文字から生成された文字の1番目の文字ということになります

そして, 奇数番目の数字は生成元の文字と同じで偶数番目の文字は生成元の数字と違うということから再帰関数を定義します

XOR

生成元の数字と違うということはXOR演算を使うと簡単に書くことが可能です

x	y	z
0	0	0
0	1	1
1	0	1
1	1	0

rec(n) = 1^rec(n-1)のように書けば異なる値を出力することが出来ます

計算量

• 空間計算量は$N$回再帰関数を実行するから$O(N)$
• 時間計算量も同様に$O(N)$

Python

class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        if K == 1:
          return 0
        if K == 2:
          return 1
        
        if K % 2 == 0:
          return 1 ^ self.kthGrammar(N-1, K//2)
        else:
          return self.kthGrammar(N-1, K//2 + 1)

C++

class Solution {
public:
    int kthGrammar(int N, int K) {
      if (K == 1) {
        return 0;
      }
      if (K == 2) {
        return 1;
      }
      if (K % 2 == 0) {
        return 1 ^ kthGrammar(N-1, K/2);
      } else {
        return kthGrammar(N-1, (K-1)/2 + 1);
      }
    }
};

解法2(iterative)

curという変数を用いて計算結果を保存すれば良いです

計算量

• 空間計算量はcur以外に新しい変数は必要としないので$O(1)$
• 時間計算量は操作を$N$回行う必要があるので$O(N)$

Python

class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
      cur = 0
      while N > 0:
        if K % 2 == 0:
          cur ^= 1
          K //= 2
        else:
          K //= 2
          K += 1
        N -= 1
      return cur

C++

class Solution {
public:
    int kthGrammar(int N, int K) {
      int cur = 0;
      while(N--) {
        if (K % 2 == 0) {
          cur ^= 1;
          K /= 2;
        } else {
          K /= 2;
          ++K;
        }
      }
      return cur;
    }
};