HackerRank The Coin Change Problem Solution

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

Hints
Solve 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

Explanation 0
There are four ways to make change for n = 4 using coins with values given by
C = [1,2,3]:

{1,1,1,1}
{1,1,2}
{2,2}
{1,3}

Table of Contents

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