Time limit exceeded in K-th symbol in Grammar (LeetCode)

Question

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

779. 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?

Answer 1

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 2²⁹ 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.