Can't understand the error of the money change problem

#1

Just one test case of the money change problem passes and rest all give a run error. Please help can’t figure out where the problem lies.

#2

hey @knownowworld please share your code through ide.codingblocks.com

#3

I have pasted the code in the ide

#4

after you paste the code, click on save and then copy the link and paste it here.

#5

#include
#include

using namespace std;

int coinWays(int *S, int n, int amt,int dp[][1000])
{

 if (amt == 0)
    return 1;

if (amt < 0)
    return 0;


if (n <=0 && amt >= 1)
    return 0;

int sum = 0;
sum = accumulate(S, S+n, sum);

if(dp[sum][amt] != 0)
{
    return dp[sum%(1000000000 + 7)][amt%(1000000000 + 7)];
}

dp[sum%(1000000000 + 7)][amt%(1000000000 + 7)] = coinWays( S, n - 1, amt,dp ) + coinWays( S, n, amt-S[n-1],dp );

return dp[sum%(1000000000 + 7)][amt%(1000000000 + 7)]%(1000000000 + 7);

}

int main() {

int t;
cin>>t;

int amt;
int n;
int *a;
int *ans = new int[t];
*ans = {0};

for(int i=0;i<t;i++)
{
int dp1[1000][1000] = {0};
cin>>n;
a = new int[n];
for(int j=0;j<n;j++)
{
cin>>a[j];
}
cin>>amt;
ans[i]=coinWays(a, n, amt,dp1);
free(a);

}

for(int i=0;i<t;i++)
cout<<ans[i]%(1000000000 + 7)<<endl;

return 0;

}

#6

https://online.codingblocks.com/app/player/68493/content/56751/5203/code-challenge

#7

@knownowworld use long long int instead of int and dont use accumulate instead write a look for addition and use modulo. moreover value of amt and sum can be as large as 10^6 and your array is of size 1000*1000 and you cant construct array of size 10^6 * !0^6 please try different approach.

#8

Here is the solution following bottom up approach https://ide.codingblocks.com/s/192969:

#9

The code link displays no code

#10
#11

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.