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.

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}