Could someone explain what did I did wrong for the question 1829D - Gold Rush. When I submitted by recursive code it gets accepted, but when I memoized the code, I am getting TLE. Thanks for explanation in advance. Below is the code,

**RECURSIVE**

```
bool solve(int n, int m) {
if(n == m) return true;
if(m > n || n % 3 != 0) return false;
int ind = n / 3;
bool left = solve(ind, m);
bool right = solve(n - ind, m);
return left || right;
}
// Invoking function
bool res = solve(n, m);
```

**MEMOIZED CODE**

```
bool solve(int n, int m, vector<int> &dp) {
if(n == m) return true;
if(m > n || n % 3 != 0) return false;
if(dp[n] != -1) return dp[n];
int ind = n / 3;
bool left = solve(ind, m, dp);
bool right = solve(n - ind, m, dp);
return dp[n] = (left || right);
}
//Invoking function
vector<int> dp(n + 1, -1);
bool res = solve(n, m, dp);
```

Auto comment: topic has been updated by Jack_sparrow_06 (previous revision, new revision, compare).Auto comment: topic has been updated by Jack_sparrow_06 (previous revision, new revision, compare).try to return in terms of dp[n] wherever possible.

the recursion take from editorial O(n^(log3 (2))) ~ O(n^0.6) but initialize dp array will take O(n)

Thankyou for the explanation, understood now.

We can solve this problem recursively. Let the current pile have n gold nuggets.

By the Master Theorem, the time complexity is O(n^0.631). Most compilers and languages optimize the recursion enough for this to pass comfortably. (The model solution in C++ runs in 15 milliseconds.)************

Here is my guess, since there is no statement in the problem which says: "the sum of all n over all test cases is less than 10^7," it is right to assume that there can be 1000 test cases where n = 10^7.

To initialize your dp array of size n + 1, it takes O(n) time. And there are t test cases. Since you are making a new array each test case, the total amount of time to make your dp array is O(n * t). n is at most 10^7 and t is at most 1000, so multiplied this is 10^10. Those many operations will certainly time out.