0

There was a similar coding question at hacker earth. The challenge ends now. I don't have that question now but my code looked like this. I passed the test cases but my code was not accepted due to large input gives this error. I have written the following code.

import java.util.*;
class TripleStep{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=10000;
        long[] memo=new long[n+1];
        Arrays.fill(memo,-1);
        long ans=StairOpr(n,memo);
        Arrays.fill(memo,-1);
        System.out.println(ans);
    }
    public static long StairOpr(int n,long[] memo){
        if(n<0){
            return 0;
        }
        else if(n==0){
            return 1;
        }
        else if(n==1){
            return 2;
        }

        else if(n==2){
            return 3;
        }
        else if(memo[n]>-1){
            return memo[n];
        }
        else
            memo[n]= (StairOpr(n-1,memo)%1000000007+StairOpr(n-2,memo)%1000000007+StairOpr(n-3,memo)%1000000007+n*n*(n+1)%1000000007)%1000000007;
            return memo[n];
    }
}

The code gives me the following error for the input value 10000.

Exception in thread "main" java.lang.StackOverflowError
    at TripleStep.StairOpr(TripleStep.java:31)
    at TripleStep.StairOpr(TripleStep.java:31)

What is the reason and what would be the solution? Since I write dynamic programming code but due to error the answer is not Submitted and I face the rejection.

imsaiful
  • 1,556
  • 4
  • 26
  • 49
  • What is this `%1000000007` supposed to do? And what value do you enter as `n`? – Tom Jun 16 '19 at 19:52
  • The result should be modulo of 1000000007 and the input value is 10000 – imsaiful Jun 16 '19 at 19:55
  • Yes I know what `%` does, but what values to do expect to get to justify that? And why do you expect your memory to support 10000 recursive method calls? Have you configured your stack appropriately? – Tom Jun 16 '19 at 19:58
  • I am in academics. I solved all question this way. Please tell me briefly why this error happen. Even cracking the coding interview book solved the dynamic programming question in this way. Thanks – imsaiful Jun 16 '19 at 20:02
  • "Please tell me briefly why this error happen." because you're doing too many recursive call. Having abort conditions means nothing when you're running out of stack space before reaching them. – Tom Jun 16 '19 at 20:04
  • There was a similar coding question at hacker earth. The challenge ends now. I don't have that question now but my code looked like this. I passed the test cases but my code was not accepted due to large input gives this error. – imsaiful Jun 16 '19 at 20:06
  • My code has proper termination condition. – imsaiful Jun 16 '19 at 20:17
  • 2
    It obviously hasn't or you wouldn't ask this question here. It isn't even that hard. Your code performs too many recursive calls due to the large input value. You can't do _everything_ with recursion, so its time to use a different approach. – Tom Jun 16 '19 at 20:29
  • Yeah, I think that question should be solved only with iteration only for large input. – imsaiful Jun 16 '19 at 20:30
  • 1
    Maybe to go with this long[] dp=new long[n+1]; dp[0]=1; dp[1]=2; dp[2]=3; for(int i=3;i<=n;i++){ dp[i]= (dp[n-1]%1000000007+dp[n-2]%1000000007+dp[n-3]%1000000007+i%1000000007*i%1000000007*(i%1000000007+1)%1000000007)%1000000007; } – imsaiful Jun 16 '19 at 20:31
  • Yes an interation approach is viable. If you found a solution to your question, then feel free to post it as an answer with a short description why and how it solves your issue. – Tom Jun 16 '19 at 21:26

1 Answers1

0

Your recursive function is creating a big stack, meaning that your function is calling itself over and over again more than your memory space can handle it.

Please, describe what is the problem that you are trying to resolve.

Daniel Karam
  • 111
  • 6
  • There was a similar coding question at hacker earth. The challenge ends now. I don't have that question now but my code looked like this. I passed the test cases but my code was not accepted due to large input gives this error. – imsaiful Jun 16 '19 at 20:05
  • Your code has stop condition but, before getting to it, your stacks become too big (over flow) and throws StackOVerflowError. I didn't understand exactly what your code does, but try to replace recursive calls by a loop condition (if possible) in order to save space solve the question. If you could describe what your code should do, maybe we could think about an efficient solution and create a better code. – Daniel Karam Jun 16 '19 at 20:27
  • 1
    Yeah, I think that question should be solved only with iteration only for large input. – imsaiful Jun 16 '19 at 20:32
  • Maybe to go with this long[] dp=new long[n+1]; dp[0]=1; dp[1]=2; dp[2]=3; for(int i=3;i<=n;i++){ dp[i]= (dp[n-1]%1000000007+dp[n-2]%1000000007+dp[n-3]%1000000007+i%1000000007*i%1000000007*(i%1000000007+1)%1000000007)%1000000007; } – imsaiful Jun 16 '19 at 20:32