instagram

Coin changing problem

by omt

Coin changing problem – Given coins of certain denominations with unlimited quantity and a total, how many minimum number of coins would be needed to form that total. Below is my video link for both bottom up and top down approach.

Input :
Coins : { 2, 3, 5, 6, 7 }
Total : 11

Output :
Min Coins : 2
Coins Used : 6,7

package com.omt.learn.algo;

import java.util.HashMap;
import java.util.Map;

public class ChangingTheCoin {

	public static void main(String[] args) {
		Map<Integer, Integer> map = new HashMap<>();
		int a[] = { 2, 3, 5, 6, 7 };
		int currentTotal = 11;

		minCoinNeeded(a, currentTotal, map);

		System.out.println("Min coins needed :" + map.get(currentTotal));
		System.out.println("Min coins needed :" + minCoinNeeded(a, currentTotal));
	}

	public static int minCoinNeeded(int a[], int total) {

		int totals[] = new int[total + 1];
		int flags[] = new int[total + 1];

		for (int i = 0; i < totals.length; i++) {
			totals[i] = Integer.MAX_VALUE;
			flags[i] = 0;
		}

		for (int i = 0; i < a.length; i++) {
			int coin = a[i];
			for (int j = coin; j < totals.length; j++) {
				int lastConinValue = j - coin;
				if (lastConinValue == 0) {
					totals[j] = 1;
					flags[j] = i;
				} else if (lastConinValue > 0) {
					if (totals[lastConinValue] != Integer.MAX_VALUE) {
						totals[j] = Math.min(1 + totals[lastConinValue], totals[j]);
						if (totals[j] == (1 + totals[lastConinValue])) {
							flags[j] = i;
						}
					}
				}
			}
		}

		System.out.println("Below conins used :");

		int i = total;
		while (i > 0) {
			System.out.println(a[flags[i]]);
			i = i - a[flags[i]];
		}

		return totals[total];

	}

	public static int minCoinNeeded(int a[], int total, Map<Integer, Integer> cache) {

		if (total == 0) {
			return 0;
		}

		if (cache.containsKey(total)) {
			return cache.get(total);
		}

		int min = Integer.MAX_VALUE - 1;

		for (int i = 0; i < a.length; i++) {

			if (total < a[i]) {
				continue;
			}

			min = minCoinNeeded(a, total - a[i], cache);
		}

		cache.put(total, ++min);
		return min;
	}

}
Share