Time limit exceeded in K-th symbol in Grammar (LeetCode) I am taking efforts to solve problem K-th Symbol in Grammar - LeetCode


  
  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:
  
  
  N will be an integer in the range [1, 30].
  K will be an integer in the range [1, 2^(N-1)].
  


My solution 

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

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

        #error cases
        if N &lt; 1 or K &lt; 1 or K &gt; 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:


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


It's a relatively fine solution, 

What might be the reason of TLE?
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.