HackerRank The Coin Change Problem Solution Yashwant Parihar, June 12, 2023August 1, 2024 In this post, we will solve HackerRank The Coin Change Problem Problem Solution. 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.Examplen = 3c = [8, 3, 1, 2]There are 3 ways to make change for n = 3: {1,1,1}, {1, 2}, and {3}. Function Description Complete the getWays function in the editor below. getWays has the following parameter(s): int n: the amount to make change for int c[m]: the available coin denominations Returns int: the number of ways to make change Input Format The first line contains two space-separated integers n and m, where: n is the amount to change m is the number of coin typesThe second line contains m space-separated integers that describe the values of each coin type. HintsSolve overlapping subproblems using Dynamic Programming (DP):You can solve this problem recursively but will not pass all the test cases without optimizing to eliminate the overlapping subproblems. Think of a way to store and reference previously computed solutions to avoid solving the same subproblem multiple times. * Consider the degenerate cases: How many ways can you make change for 0 cents? – How many ways can you make change for >0 cents if you have no coins? * If you’re having trouble defining your solutions store, then think about it in terms of the base case (n= 0). – The answer may be larger than a 32-bit integer. Sample Input 0 4 3 1 2 3 Sample Output 0 4 Explanation 0There are four ways to make change for n = 4 using coins with values given byC = [1,2,3]: {1,1,1,1} {1,1,2} {2,2} {1,3} HackerRank The Coin Change Problem Solution The Coin Change Problem C Solution #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> long cache[51][251]; //Assumes coins are in sorted order. long ways(int N, int M, int * coins){ if(N < 0 || M < 0) return 0; if(cache[M][N] == -1){ //Do actual computing, store result in cache[N] long way = 0; for(int m = M; m > 0; m--){ int c = coins[m-1]; for(int n = N - c; n >= 0; n -= c){ way += ways(n,m-1,coins); } } cache[M][N] = way; } return cache[M][N]; } int compare_ints (const void *a, const void *b) { const int *da = (const int *) a; const int *db = (const int *) b; return (*da > *db) - (*da < *db); } int main() { //setup cache for(int i = 0; i <= 250; i++){ for(int j = 0; j <= 50; j++){ if(i==0) { cache[j][i] = 1; } else if (j == 0) { cache[j][i] = 0; } else { cache[j][i] = -1; } } } /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int N, M; scanf("%d %d", &N, &M); int * coins = (int*) calloc(M, sizeof(int)); for(int m = 0; m < M; m++){ scanf("%d",&coins[m]); } qsort(coins,M,sizeof(int),compare_ints); printf("%ld\n",ways(N,M,coins)); return 0; } The Coin Change Problem C++ Solution #include<bits/stdc++.h> #define nl '\n' using namespace std; typedef long long ll; ll W[251][251][51]/*memoize*/;int arr[55]; ll way(int sum,int num,int val) { if(W[sum][num][val] != -1) return (ll)W[sum][num][val]; if(num * arr[val] > sum){ W[sum][num][val] = 0; return 0; } if(num*arr[val] == sum){ W[sum][num][val] = 1; return 1; } if(val == 1){ if((sum - num*arr[val])%arr[0] == 0) { W[sum][num][val]=1; return 1; } else { W[sum][num][val]=0; return 0; } } ll tot = 0;int i = 0; while(i*arr[val-1] <= sum-num*arr[val]){ tot = (ll)tot + way(sum-num*arr[val],i,val-1); i++; } W[sum][num][val] = tot; return tot; } int main() { ios::sync_with_stdio(0);cin.tie(0); int n,m,i; cin>>n>>m; for(i=0;i<m;i++) cin>>arr[i]; if(m==1){ if(n%arr[0] == 0) cout<<1<<nl; else cout<<0<<nl; return 0; } sort(arr,arr+m); ll total = 0;i=0; memset(W,-1,sizeof(W)); while(i*arr[m-1] <= n){ total = (ll)total + way(n,i,m-1); i++; } cout<<total<<nl; return 0; } The Coin Change Problem C Sharp Solution using System; using System.Collections.Generic; using System.IO; class Solution { static void Main(String[] args) { string str = Console.ReadLine(); string[] terms = str.Split(' '); int n = Convert.ToInt32(terms[0]); int m = Convert.ToInt32(terms[1]); int[] coins = new int[m]; str = Console.ReadLine(); terms = str.Split(' '); for (int i = 0; i < m; i++) { coins[i] = Convert.ToInt32(terms[i]); } long[] opt = new long[n + 1]; opt[0] = 1; Array.Sort(coins); for (int i = 0; i < m; i++) { for (int j = 1; j <= n; j++) { if (j - coins[i] >= 0) { opt[j] += opt[j - coins[i]]; } } } Console.WriteLine(opt[n]); } } The Coin Change Problem Java Solution import java.util.Scanner; import java.util.HashMap; // Use a HashMap as a cache to speed up runtime // Must use "long" instead of "int" to avoid integer overflow public class Solution { public static void main(String[] args) { /* Save input */ Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int m = scan.nextInt(); int [] coins = new int[m]; for (int i = 0; i < m; i++) { coins[i] = scan.nextInt(); } scan.close(); System.out.println(numWays(n, coins)); } public static long numWays(int n, int [] coins) { if (n < 0) { return 0; } return numWays(n, coins, 0, new HashMap<String, Long>()); } public static long numWays(int n, int [] coins, int coinNumber, HashMap<String, Long> cache) { /* Check our cache */ String key = n + "," + coinNumber; if (cache.containsKey(key)) { return cache.get(key); } /* Base case */ if (coinNumber == coins.length - 1) { if (n % coins[coinNumber] == 0) { cache.put(key, 1L); return 1; } else { cache.put(key, 0L); return 0; } } /* Recursive case */ long ways = 0; for (int i = 0; i <= n; i += coins[coinNumber]) { ways += numWays(n - i, coins, coinNumber + 1, cache); } /* Cache and return solution */ cache.put(key, ways); return ways; } } The Coin Change Problem JavaScript Solution var test = (function() { function makeArr(n, isArr) { var arr = []; for (var i = 0; i < n; i++) { arr[i] = arr[i] || []; for (var j = 0; j < n; j++) { arr[i][j] = (isArr) ? [] : 0; } } return arr; } function coins (S, m, n) { var i, j, x, y; var table = makeArr(n+1, m); // Fill the enteries for 0 value case (n = 0) for (i=0; i<m; i++) table[0][i] = 1; // Fill rest of the table enteries in bottom up manner for (i = 1; i < n+1; i++) { for (var j = 0; j < m; j++) { // Count of solutions including S[j] x = (i-S[j] >= 0)? table[i - S[j]][j]: 0; // Count of solutions excluding S[j] y = (j >= 1)? table[i][j-1]: 0; // total count table[i][j] = x + y; } } return table[n][m-1]; } return { coins: coins } })(); function processData(input) { var arr = input.split('\n'); arr[0] = arr[0].split(' '); arr[1] = arr[1].split(' ').map(function(el){return parseInt(el)}); console.log(test.coins(arr[1], parseInt(arr[0][1]), parseInt(arr[0][0]))); //Enter your code here } process.stdin.resume(); process.stdin.setEncoding("ascii"); _input = ""; process.stdin.on("data", function (input) { _input += input; }); process.stdin.on("end", function () { processData(_input); }); The Coin Change Problem Python Solution import sys arr = list(map(int, sys.stdin.readline().split(', '))) s = int(sys.stdin.readline()) sol = [0]*(s+1) sol[0] = 1 for num in arr: for i in range(num, s+1): sol[i] += sol[i - num] print(sol[-1]) c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython