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

Question

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

Answer 1

Thanks for the like

Answer 2

Ahoj,
Congratulations for Your new level 14

Answer 3

Recursion will not work with big numbers

Answer 4

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 🤭

Answer 5

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.

Answer 6

6/6 with the help of the "while" cycle.
https://code.sololearn.com/cfqO1I0QBFIB/?ref=app

Answer 7

Yes you have to remove recursion entirely try DP with bottom up approach.
What are the input constraints??

Answer 8

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

Answer 9

Igor Kostrikin Milind Yadav
I'll try. Thanks

Answer 10

Milind Yadav thank you!

Answer 11

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

Answer 12

Milind Yadav I tried it, result shows me 5/6 right, but last test is wrong... 🤔

Answer 13

What do u mean by 5/6

Answer 14

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;
}

Answer 15

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;
}