+ 3

# Hofstadter's Q-Sequence. Where's an error?

Hofstadter's Q-Sequence is a sequence of numbers where every integer above zero has a corresponding q-sequence value. You can determine the q-sequence value from a formula that tells you how far back in the sequence to go and add two values together. The first two values of the sequence are Q(1) = 1 and Q(2) = 1, and every number above 2 can be expressed according to the following formula (where n is your input value): Q(n) = Q(n - Q(n - 1)) + Q(n - Q(n -2)) Task: Given an integer value input, determine and output the corresponding q-sequence value. Input Format: A positive integer value. Output Format: A positive integer value that represents the value in the q-sequence that the input holds My code show result as 4/6 https://code.sololearn.com/czBMEFJh6744/?ref=app

13th Jul 2020, 8:05 PM
Jhon Doe
15 Antworten
+ 6
Thanks for the like
18th Aug 2020, 6:15 PM
Egor Tonchev(EGO)
+ 5
Ahoj, Congratulations for Your new level 14
19th Aug 2020, 5:46 PM
Egor Tonchev(EGO)
+ 2
Recursion will not work with big numbers
14th Jul 2020, 2:53 AM
Igor Kostrikin
+ 2
I have the same problem, so it means that lru_cache won’t work with the bigger numbers? Why exactly, can someone explain? I thought it is good for big numbers 🤭
14th Jul 2020, 11:32 PM
Andrea Šafráneková
+ 2
Andrea Šafráneková It'll work but due to recursion without memoization time complexity will be O(2^n) and with memoization it'll be linear time but you would have to compute again and again....so it's better if u construct a DP Table.
15th Jul 2020, 12:00 AM
+ 2
6/6 with the help of the "while" cycle. https://code.sololearn.com/cfqO1I0QBFIB/?ref=app
25th Nov 2022, 6:16 AM
+ 1
Yes you have to remove recursion entirely try DP with bottom up approach. What are the input constraints??
14th Jul 2020, 3:01 AM
+ 1
Milind Yadav "What do u mean by 5/6. Hofstadter's Q-Sequence is the Sololearn's task. After you wright code Sololearn start six test and return it's result. Sololearn doesn't show input format and doesn't show error an your code, so that the author of the code can think for himself where he made a mistake
14th Jul 2020, 7:25 AM
Jhon Doe
+ 1
Igor Kostrikin Milind Yadav I'll try. Thanks
14th Jul 2020, 7:25 AM
Jhon Doe
+ 1
15th Jul 2020, 10:34 AM
Andrea Šafráneková
0
Please give the inputs and corresponding expected output where your code fails. Your code looks fine to me but you can add memoization to it, instead redundant recursion. here is the code with memoization https://code.sololearn.com/cGTgSx4LlpCj/#py
13th Jul 2020, 8:55 PM
0
Milind Yadav I tried it, result shows me 5/6 right, but last test is wrong... 🤔
13th Jul 2020, 9:53 PM
Jhon Doe
0
What do u mean by 5/6
13th Jul 2020, 9:54 PM