Hofstadter's Q-Sequence. Where's an error? | Sololearn: Learn to code for FREE!
+ 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
Jhon Doe - avatar
15 Antworten
+ 6
Thanks for the like
18th Aug 2020, 6:15 PM
Egor Tonchev(EGO)
Egor Tonchev(EGO) - avatar
+ 5
Ahoj, Congratulations for Your new level 14
19th Aug 2020, 5:46 PM
Egor Tonchev(EGO)
Egor Tonchev(EGO) - avatar
+ 2
Recursion will not work with big numbers
14th Jul 2020, 2:53 AM
Igor Kostrikin
Igor Kostrikin - avatar
+ 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á
Andrea Šafráneková - avatar
+ 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
Milind Yadav
Milind Yadav - avatar
+ 2
6/6 with the help of the "while" cycle. https://code.sololearn.com/cfqO1I0QBFIB/?ref=app
25th Nov 2022, 6:16 AM
Vlad K
Vlad K - avatar
+ 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
Milind Yadav
Milind Yadav - avatar
+ 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
Jhon Doe - avatar
+ 1
Igor Kostrikin Milind Yadav I'll try. Thanks
14th Jul 2020, 7:25 AM
Jhon Doe
Jhon Doe - avatar
+ 1
Milind Yadav thank you!
15th Jul 2020, 10:34 AM
Andrea Šafráneková
Andrea Šafráneková - avatar
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
Milind Yadav
Milind Yadav - avatar
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
Jhon Doe - avatar
0
What do u mean by 5/6
13th Jul 2020, 9:54 PM
Milind Yadav
Milind Yadav - avatar
0
For cpp.. calculate an array from very begin up to destination.. and no recursion will be needed. #include <iostream> using namespace std; int main() { int n, i, k[1000]={1,1}; cin>>n; for(i=2; i<=n; i++) k[i]=k[i-k[i-1]]+k[i-k[i-2]]; cout << k[n-1]; return 0; }
2nd Jan 2024, 7:03 PM
đíđÁĐÇđ│đÁđ╣ đŤđ░đŻĐüđ║đżđ▓
đíđÁĐÇđ│đÁđ╣ đŤđ░đŻĐüđ║đżđ▓ - avatar
0
For cpp.. calculate an array from very begin up to destination.. and no recursion will be needed. #include <iostream> using namespace std; int main() { int n, i, k[1000]={1,1}; cin>>n; for(i=2; i<=n; i++) k[i]=k[i-k[i-1]]+k[i-k[i-2]]; cout << k[n-1]; return 0; }
2nd Jan 2024, 7:03 PM
đíđÁĐÇđ│đÁđ╣ đŤđ░đŻĐüđ║đżđ▓
đíđÁĐÇđ│đÁđ╣ đŤđ░đŻĐüđ║đżđ▓ - avatar