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.

HackerRank The Coin Change Problem solution


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])
    

{"mode":"full","isActive":false}


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();
    }
    
}

{"mode":"full","isActive":false}


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;
}

{"mode":"full","isActive":false}


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;
}

{"mode":"full","isActive":false}