In this HackerRank The Coin Change Problem solution you 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.
Problem solution in Python.
amount, _ = [int(item) for item in input().strip().split()] coins = [int(item) for item in input().strip().split()] dp_arr = [1] + [0] * amount for coin in coins: for idx in range(coin, amount+1): dp_arr[idx] += dp_arr[idx - coin] print(dp_arr[-1])
Problem solution in Java.
import java.io.*; import java.util.*; public class Solution { public static class MyScanner { BufferedReader br; StringTokenizer st; public MyScanner() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } String nextLine(){ String str = ""; try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return str; } } public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ MyScanner sc = new MyScanner(); PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out)); int n = sc.nextInt(); int m = sc.nextInt(); long table[][] = new long[n+10][m+10]; int coinvalues[] = new int[m+10]; long noexchange[] = new long[n+10]; for (int i=1;i<=m;i++) { coinvalues[i] = sc.nextInt(); } for(int i = 0; i <= n; i++) { for(int j = 0; j <= m; j++) { if(i==0){ table[i][j] = 1; } else if(j==0){ table[i][j] = 0; } else if(coinvalues[j] > i) { table[i][j] = table[i][j-1]; } else { table[i][j] = table[i-coinvalues[j]][j] + table[i][j-1]; } } } out.println(table[n][m]); out.close(); } }
Problem solution in C++.
#include <cmath> #include <cstdio> #include <cstring> #include <vector> #include <iostream> #include <sstream> #include <algorithm> #include <cstdint> #include <set> #include <unordered_map> using namespace std; using std::set; using std::unordered_map; unordered_map<int, unordered_map<int, int> > maxCostToMinIndexToCount; // Cache for memoization template<typename K, typename V> bool isKeyPresent(const unordered_map<K,V>& map, const K& key) { return (map.find(key) != map.end()); } void addToMap(int maxCost, int minIndex, int count) { if (!isKeyPresent(maxCostToMinIndexToCount, maxCost)) { unordered_map<int, int> d; maxCostToMinIndexToCount.insert({{maxCost, d}}); } maxCostToMinIndexToCount[maxCost].insert({{minIndex, count}}); } int computeCountHelper(int maxCost, vector<int> coinDenominations, int minIndex) { if (isKeyPresent(maxCostToMinIndexToCount, maxCost)) { const auto d = maxCostToMinIndexToCount[maxCost]; if (isKeyPresent(d, minIndex)) { return d.at(minIndex); } } int count = 0; int numDenominations = coinDenominations.size(); if (minIndex == numDenominations - 1) { int tmp = maxCost % coinDenominations[minIndex]; count = (tmp == 0) ? 1 : 0; addToMap(maxCost, minIndex, count); return count;; } auto denom = coinDenominations[minIndex]; auto no = maxCost / denom; for (auto j = 0; j <= no; j++) { count += computeCountHelper(maxCost - j * denom, coinDenominations, minIndex + 1); } addToMap(maxCost, minIndex, count); return count; } int main() { vector<int> coinDenominations; string denomsStr; std::getline(cin, denomsStr); std::istringstream ss(denomsStr); std::string token; while(std::getline(ss, token, ',')) { coinDenominations.push_back(stoi(token)); } int N; cin >> N; auto count = computeCountHelper(N, coinDenominations, 0); cout << count << endl; return 0; }
Problem solution in C.
#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> unsigned long int coinchange(int W,int n) { int a[n]; int i,w,j; unsigned long int K[n][W+1]; for(i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<n;i++) for(int j=0;j<=W;j++) { K[i][j]=0; } for(i=0;i<=W;i++) { if(i%a[0]==0) K[0][i]=1; } // Build table K[][] in bottom up manner for (i = 1; i<n; i++) for (w = 0; w <= W; w++) { if (w-a[i]>=0) K[i][w] = K[i][w-a[i]] + K[i-1][w]; else K[i][w] = K[i-1][w]; } return K[n-1][W]; } int main() { int n,W; scanf("%d %d",&W,&n); printf("%lu",coinchange(W,n)); /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0; }