[LeetCode][Kotlin] 779. K-th Symbol in Grammar

779. K-th Symbol in Grammar

We build a table of n rows (1-indexed). We start by writing 0 in the 1st row. 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.

• For example, for n = 3, the 1st row is 0, the 2nd row is 01, and the 3rd row is 0110.

Given two integer n and k, return the kth (1-indexed) symbol in the nth row of a table of n rows.

n개 행(1-인덱스)의 표를 만듭니다. 1번째 행에 0을 쓰는 것으로 시작합니다. 이제 모든 후속 행에서 이전 행을 보고 0이 나오는 모든 곳을 01로, 1이 나오는 모든 곳을 10으로 바꿉니다. 
- 예를 들어, n = 3의 경우 1번째 행은 0이고, 2번째 행은 01이고, 3번째 행은 0110입니다. 

두 개의 정수 n과 k가 주어지면 n개 행의 표에서 n번째 행에 있는 k번째(1-인덱스) 심볼을 반환합니다.

 

Example 1:

Input: n = 1, k = 1

Output: 0

Explanation: row 1: 0

 

Example 2:

Input: n = 2, k = 1

Output: 0

Explanation: 

row 1: 0

row 2: 01

 

Example 3:

Input: n = 2, k = 2

Output: 1

Explanation: 

row 1: 0

row 2: 01

 

Constraints:

• 1 <= n <= 30
• 1 <= k <= 2^(n - 1)

---

코드

• 이진 트리
• k 가 mid 보다 작거나 같으면, k 는 왼쪽 구간에 있으므로 right 를 mid 로 설정한다.
• k 가 mid 보다 크면, k 는 오른쪽 구간에 있으므로 left 를 mid + 1 로 설정하고 현재 심볼을 반전한다.

class Solution {
    fun kthGrammar(n: Int, k: Int): Int {
        var cur = 0
        var left = 1
        var right = Math.pow(2.0, (n - 1).toDouble()).toInt()

        for (i in 1..n - 1) {
            val mid = (left + right) / 2
            
            if (k <= mid) {
                right = mid
            } else {
                left = mid + 1
                if (cur == 1) cur = 0 else cur = 1
            }
        }

        return cur
    }
}