Code coatch [Hofstadter's Q-Sequence]

Question

I made a program that is giving correct output for test case 1and 2 but failing test case 3-6. Test cases 3-6 are hidden so I don't know in which case it is failing. How can I correct it if I don't know what the problem is?

Answer 1

Your code takes too long for N>30, so it timeouts and prints an error.

Try using memoization to speed up your code.
https://www.geeksforgeeks.org/memoization-1d-2d-and-3d/

Answer 2

How much maximum value of 'n' you think for which your code can calculate Q(n) ?

Q(n)
/ \
Q(n-1) Q(n-2)
/ \ / \
Q(n-2) Q(n-3) Q(n-3) Q(n-4)
. . . .
. . . .

Seems like too much function calls there, which is making it slow and giving TLE(time limit exceeded).
Possible solution of it can be using basic dynamic programming, you can see that you are calculating Q(n-2) & Q(n-3) multiple times(In above structure I made) so if you can store it somewhere so you not calculate it multiple times and avoid unnecessary space and time, thats how you can make your program more faster & efficient.

Answer 3

That is a pro challenge. I sent you a private message, because the solutions to the challenges should not be posted.

I'll rewrite it here. You can send me a resume of the challenge along with your solution, and I'll try to help.

Answer 4

Thanks everyone.

Answer 5

Ankur Singh Oli 🐍 Memoization:
Qn = {1:1, 2:1}

Answer 6

what about test case 6.. I managed to get all tests correct except for that one?!