DP: Coin Change HackerRank Solution

DP: Coin Change HackerRank Solution
Source : https://www.hackerrank.com/challenges/ctci-coin-change

Given a number of dollars and an array of denominations of coins, determine how many ways you can make change. For example, making change for dollars from coin denominations , there are ways to make change:

1 1 1 1 1 1 1 1 1 1 1  1 1 5 5   1 1 1 1 1 1 1 51 1 1 1 1 1 1 1 1 1 2 2 5 51 1 1 1 1 1 1 1 2 2 1 1 101 1 1 1 1 1 2 2 2 2 101 1 1 1 2 2 2 2  2 2 2 1 51 1 2 2 2 2 2        2 2 1 1 1 52 2 2 2 2 2           2 1 1 1 1 1 5

Hints:

• You can solve this problem recursively, but you must optimize your solution to eliminate overlapping subproblems using Dynamic Programming if you wish to pass all test cases. More specifically, think of ways to store the checked solutions and use the stored values to avoid repeatedly calculating the same values.
• Think about the degenerate cases:
  • How many ways can you make change for dollars?
  • How many ways can you make change for less than dollars if you have no coins?
• If you are having trouble defining the storage for your precomputed values, then think about it in terms of the base case .

Function Description

Complete the function makeChange in the editor below. It should return the integer representing the number of ways change can be made.

makeChange has the following parameter(s):

• n: an integer, the amount to change
• coins: an array of integers representing coin denominations

Input Format

The first line contains two space-separated integers, and , the amount to make change for and the number of denominations of coin.
The second line contains space-separated integers describing the denominations of each .

Constraints

• The list of coins contains distinct integers where each integer denotes the dollar value of a coin available in an infinite quantity.

Output Format

Print a single integer denoting the number of ways we can make change for dollars using an infinite supply of our types of coins.

Sample Input 0

4 31 2 3 

Sample Output 0

4

Explanation 0
For and there are four solutions:

Thus, we print on a new line.

Sample Input 1

10 42 5 3 6

Sample Output 1

5

Explanation 1
For and there are five solutions:

Thus, we print on a new line.

Source : https://www.hackerrank.com/challenges/ctci-coin-change

Solution

	// Karthikalapati.blogspot.com
	// Use a HashMap as a cache to speed up runtime
	// Must use "long" instead of "int" to avoid integer overflow
	static long ways(int n, int[] coins) {
	if (n < 0) {
	return 0;
	}
	return numWays(n, coins, 0, new HashMap<String, Long>());
	}
	private 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;
	}