Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/779.html

779. K-th Symbol in Grammar

Level

Medium

Description

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.)

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

Solution

Observe each row. It can be seen that row N + 1 is obtained from row N by copying the content of row N and then concatenating the reversed content of row N. Row 1 is “0” and row 2 is “01”, which are quite obvious. For N >= 2, the left half of the content in row N and the right half of the content in row N are reversed to each other, so the content of row N + 1 is obtained in the way mentioned above.

This problem can be solved without using N, and only K is needed. While K is greater than 1, replace K with its complement, where the complement of K is defined as the smallest positive integer C such that K + C = 2^M + 1 where M is a positive integer.

Each time K is replaced with its complement, does the symbol change? Calculate log = Math.ceil(Math.log(K) / Math.log(2)). If log is odd, then the symbol changes. Otherwise, the symbol remains unchanged.

After K becomes 1, count the number of times that the symbol is changed. Since the symbol at index 1 is 0, if the symbol is changed odd number of times, return 1. Otherwise, return 0.

  • class Solution {
    public int kthGrammar(int N, int K) {
        int reverseCount = 0;
        while (K > 1) {
            int log = (int) Math.ceil(Math.log(K) / Math.log(2));
            int power2 = (int) Math.pow(2, log);
            K = power2 + 1 - K;
            if (log % 2 == 1)
                reverseCount++;
        }
        return reverseCount % 2;
    }
}

  • // OJ: https://leetcode.com/problems/k-th-symbol-in-grammar/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int kthGrammar(int n, int k) {
        if (n == 1) return 0;
        return k <= (1 << (n - 2)) ? kthGrammar(n - 1, k) : (1 - kthGrammar(n - 1, k - (1 << (n - 2))));
    }
};

  • class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        return (k - 1).bit_count() & 1

############

class Solution(object):
    def kthGrammar(self, N, K):
        """
        :type N: int
        :type K: int
        :rtype: int
        """
        if K == 1:
            return 0
        if K <= (1 << (N - 2)):
            return self.kthGrammar(N - 1, K)
        else:
            return 1 - self.kthGrammar(N - 1, K - (1 << (N - 2)))

  • func kthGrammar(n int, k int) int {
	return bits.OnesCount(uint(k-1)) & 1
}

All Problems

All Solutions