In this The Coin Change Problem HackerRank solution, we have Given an amount and the denominations of coins available, determine how many ways change can be made for amount. There is a limitless supply of each coin type. We need to Complete the getWays function in the editor below.
The Coin Change Problem HackerRank solution
I will Provide solution in Multiple programming languages for you. If you are not able to find the code in required language then please share in comments so that our team can help you.
Problem Solution in Java
public static long getWays(int n, List<Long> cs) {
long[] t = new long[n+1];
t[0] = 1;
for (long c : cs)
for (int i = (int)c; i <= n; i++)
t[i] += t[i-(int)c];
return t[n];
}Problem Solution in C++
long getWays(int n, vector<long> c) {
vector<vector<long>> table;
sort(c.begin(), c.end());
for (int i = 0; i < c.size(); i++) {
vector<long> coinrow(n+1);
table.push_back(coinrow);
}
for (int j = 0; j <= n; j++){
if (j % c[0] == 0) {
table[0][j] = 1;
} else {
table[0][j] = 0;
}
}
for (int i = 1; i < c.size(); i++){
for (int j = 0; j <= n; j++){
if (c[i] > j){
table[i][j] = table[i-1][j];
} else {
long result = j - c[i];
long value = table[i-1][j] + table[i][result];
table[i][j] = value;
}
}
}
return table[c.size()-1][n];
}Problem Solution in C
long getWays(int n, int c_count, long* c) {
long *dp = (long *)calloc(n + 1, sizeof(long));
dp[0] = 1;
for (int i = 0; i < c_count; i++)
{
for (int j = c[i]; j <= n; j++)
{
dp[j] += dp[j - c[i]];
}
}
long result = dp[n];
free(dp);
return result;
}Problem Solution in Python
da=dict()
def process(arr,ind,n):
res=0
if (ind,n) in da:
return da[(ind,n)]
if ind==len(arr):
res=1 if n==0 else 0
else:
for i in range(n//arr[ind]+1):
res+=process(arr,ind+1,n-arr[ind]*i)
da[(ind,n)]=res
return res
def getWays(arr, n):
if not arr or len(arr)==0 or n<0:
return 0
return process(arr,0,n)Solve original Problem on HackerRank here. Checkout more HackerRank Problems