Hofstadter's Q-Sequence

Question

Doesn't pass all tests. Where did I make a mistake and how can this code be optimized?

value = int(input())
def Q(n):
if n == 1 or n == 2: return 1
else:
return Q(n - Q(n - 1)) + Q(n - Q(n - 2))
print(Q(value))

Answer 1

Your code is correct, but it will be very slow - each time the function is called with n > 2 it calls four other Q functions, that themselves call four other and so on. As a result the total number of calls is least Fib(n) ~ 1.6**n (this is a very conservative lower bound, calculating the exact number of calls would be an interesting problem)

Please think how to modify your solution so that the time it takes is linear in n.

Answer 2

Mostafa Ehab i just create list for saved "Q results"
https://code.sololearn.com/cQ9fb4uDIeCI/?ref=app

Answer 3

👿BAD BOY! There is no error, but the hidden tests doesn't pass

Answer 4

👿BAD BOY! This code only passed tests 1 and 2, and failed the rest

Answer 5

👿BAD BOY! code simulator in the community, "Hofstadter's Q-Sequence"

Answer 6

I had the same problem and I reached a solution called memorization here it is https://www.geeksforgeeks.org/memoization-1d-2d-and-3d/

Answer 7

But the problem is I passed all tests except for the last one and I don’t know why.. very annoying !

Answer 8

DenseAcid Oh thank you your first line was what I’m missing!.. here is my code I think you can remove some lines of your code if you take a look at it

https://code.sololearn.com/cZR7km8bsj1u/?ref=app