0
\$\begingroup\$

I am taking efforts to solve problem K-th Symbol in Grammar - LeetCode

  1. K-th Symbol in Grammar

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

My solution

class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        #replace function
        def replace(row: "List[int]") -> "List[int]":
            """
            rtype: row 
            """
            for i in range(len(row)):
                print(row[i])
                if row[i] == 0: #0 -> 01
                    row.insert(2*i+1, 1)
                elif row[i] == 1: #1 -> 10
                    row.insert(2*i+1, 0)
            return row 

        #helper function 
        def helper(N: int) -> "List(int)":
            """
            rtype:the last row 
            """
            #error case 
            if N < 1: return []
            #base case
            if N == 1:
                res = [0]
                return res 
            elif N > 1:
                return replace(helper(N-1))

        #error cases
        if N < 1 or K < 1 or K > 2**(N-1) : return None 
        #recur        
        row = helper(N)
        #logging.debug(f"row: {row}")
        return row[K-1]

Unfortunately it reported Time Limit Exceeded

Last executed input: 30 434991989

Review my solution:

  1. employed tail recursion return replace(helper(N-1))
  2. did not create a new row

It's a relatively fine solution,

What might be the reason of TLE?

\$\endgroup\$
0
\$\begingroup\$

It makes little difference how the row is constructed, the problem is intentionally designed such that constructing the row at all will lead to TLE. Consider that for N=30, the row would have 229 elements, that's no good. This is usually the case with competitive programming problems, they are made to make the straightforward solutions fail, that is what makes it competitive.

There are a few ways you could go about solving it, for example, you could recognize that the sequence produced is the Thue-Morse sequence, which has a simple formula to calculate an element at a given index without generating the whole sequence up to that index. The result does not depend on N.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.