+ 4

Hofstadter's Q-Sequence +100 XP pro

I am trying to solve the Code Coach problem below, but when I run it, the system tests 5 different inputs and tell me that only 2 ran properly. I am using a recursive method and my code is available in the bottom in Java. I fear that the SoloLearn online compiler is not fast enough to make all the interactions, then I would like to know if there is a lighter code possible to be written or if my code is wrong. Hofstadter's Q-Sequence +100 XP 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. Sample Input: 5 Sample Output: 3 ====================================================================== The Sequence can be seen in the following website in case you wish to compare it with the code's results: https://oeis.org/A005185/list ====================================================================== import java.util.Scanner; public class Qsequence { static int Q(int n){ if(n == 1 || n == 2){ return 1; } return Q(n - Q(n - 1)) + Q(n - Q(n -2)); } public static void main(String[] args) { Scanner scan = new Scanner(System.in); int x = scan.nextInt(); int output = Q(x); System.out.println(output); } } https://code.sololearn.com/cipdSnAeQ78k/#java

21st Sep 2020, 8:20 PM
Lucas Kliemczak
Lucas Kliemczak - avatar
2 Answers
+ 7
Yaa! When you put big numbers, the execution time runs out and hence we see "No output." To fix that, use memoization! >> What is memoization? It is a method by which we allow our program to speed up! In case we see the same number again then let the system get the direct answer instead of following the whole process again! This will reduce calculations and hence, less execution time! >> How can we do that? Use a list or a hashmap 🙌 Or search about it online👌 Here's the reference: https://www.interviewcake.com/concept/java/memoization
21st Sep 2020, 8:37 PM
Namit Jain
Namit Jain - avatar
+ 5
Either use memoization or write the code in iterative fashion.
21st Sep 2020, 8:49 PM
Kevin ★