HackerRank The Coin Change Problem solution

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.

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 types
The second line contains m space-separated integers that describe the values of each coin type.

HackerRank The Coin Change 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])

The Coin Change 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;
}