# Hackerrank DP problem

I’m solving this Coin Change problem on Hackerrank. I recently started doing DP but stuck on this question.
This is my code:

``````#include<iostream>
using namespace std;
int main()
{
int total, n;
cin>>total>>n;
int coins[n];
for(int i=0; i<n; i++) cin>>coins[i];

int ways[n][total+1] = {0};
ways[0][0]=1;
for(int i=1; i<=total; i++)
if (i % coins[0] == 0)
ways[0][i]=1;

for(int i=1; i<n; i++)
{
for(int j=0; j<=total; j++)
{
if(coins[i]>j)
ways[i][j] = ways[i-1][j];
else
ways[i][j] = ways[i-1][j] + ways[i][j-coins[i]];
}
}

cout<<ways[n-1][total];

return 0;
}
``````

It gets accepted for most of the test cases but gives weird output on

``````15 24
49 22 45 6 11 20 30 10 46 8 32 48 2 41 43 5 39 16 28 44 14 4 27 36
``````

Overflow - try changing the type of `ways` to `long long int`.

Edit:

Hmmm … maybe that’s not sufficient - getting weird (but at least not negative!) numbers with this.

1 Like

It still produces garbage values…

Changing it to use a `vector` seems to be work: presumably a problem with the two-dimensional array not being zero’d initially correctly:

``````    vector<vector<long long int>> ways(n, vector<long long int>(total+1));
``````

Edit:

Or alternatively:

``````    long long int ways[n][total+1] = {};
``````

I’m a bit confused as to why the original was not working - according to this, it seems like maybe it should. Although perhaps it’s because dynamic arrays are non-standard. Dunno

3 Likes

yes, it works. Thanks.

1 Like

I wrote a very simple program to demonstrate what goes wrong in your program.

Code 1
``````	#include <iostream>

int main (void) {
int m, n;
std::cin >> m >> n;
int A[m][n] = {0};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (A[i][j] != 0) {
std::cout << i << " " << j << std::endl;
}
}
}
return 0;
}
``````

I assumed that `line 6` creates a ‘variable length array’, which is valid in C, but not valid in C++ and assigns value `0` to all its elements, which straight off causes a compilation error in C:

Code 2
``````	#include <stdio.h>

int main (void) {
int m, n;
scanf("%d %d", &m, &n);
int A[m][n] = {0};

return 0;
}
``````
Errors and warnings
``````progc.c: In function 'main':
progc.c:6:2: error: variable-sized object may not be initialized
int A[m][n] = {0};
^
progc.c:6:17: warning: excess elements in array initializer
int A[m][n] = {0};
^
progc.c:6:17: note: (near initialization for 'A[0]')
progc.c:6:2: warning: excess elements in array initializer
int A[m][n] = {0};
^
progc.c:6:2: note: (near initialization for 'A')
``````

but somehow doesn’t cause any compilation error in C++.

However, it does cause a run time error. I tested `Code 1` with:

Input
``````1
500000
``````

Guess what?

Output
``````0 498295
0 498296
0 498297
.
.
.
``````

Clearly, it doesn’t assign `0` to all the elements of the array in all cases!

Your task (using `Code 1`) : Try to figure out the upper-bound of the dimensions so that the program successfully assigns `0` to all the elements. You may try out the fun way by trying out a binary search on the required dimensions or the foolproof way, by going through the assembly (it’s painful but highly rewarding).

[ Warning: The program crashes when you exceed the stack size. ]

Hope this helps.

2 Likes