Coin Change Problem Code Implementations
Complete Coin Change Problem code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Coin Change Problem Guide · Launch Interactive Visualizer
C++ Implementation
// Coin Change Implementation in C++
// Problem: Find minimum number of coins needed to make amount
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <climits>
class CoinChange {
public:
// Recursive approach (exponential time)
static int coinChangeRecursive(const std::vector<int>& coins, int amount) {
if (amount == 0) return 0;
if (amount < 0) return -1;
int minCoins = INT_MAX;
for (int coin : coins) {
int result = coinChangeRecursive(coins, amount - coin);
if (result != -1) {
minCoins = std::min(minCoins, result + 1);
}
}
return minCoins == INT_MAX ? -1 : minCoins;
}
// Top-down DP with memoization
static int coinChangeMemo(const std::vector<int>& coins, int amount) {
std::unordered_map<int, int> memo;
return dp(coins, amount, memo);
}
private:
static int dp(const std::vector<int>& coins, int target, std::unordered_map<int, int>& memo) {
if (target == 0) return 0;
if (target < 0) return -1;
if (memo.find(target) != memo.end()) return memo[target];
int minCoins = INT_MAX;
for (int coin : coins) {
int result = dp(coins, target - coin, memo);
if (result != -1) {
minCoins = std::min(minCoins, result + 1);
}
}
int result = minCoins == INT_MAX ? -1 : minCoins;
memo[target] = result;
return result;
}
public:
// Bottom-up DP with tabulation
static int coinChangeTabulation(const std::vector<int>& coins, int amount) {
std::vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i && dp[i - coin] != INT_MAX) {
dp[i] = std::min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
// Coin change with reconstruction (which coins to use)
struct CoinChangeResult {
int minCoins;
std::vector<int> coins;
CoinChangeResult(int min, const std::vector<int>& c) : minCoins(min), coins(c) {}
};
static CoinChangeResult coinChangeWithReconstruction(const std::vector<int>& coins, int amount) {
std::vector<int> dp(amount + 1, INT_MAX);
std::vector<int> usedCoins(amount + 1, -1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i && dp[i - coin] != INT_MAX && dp[i - coin] + 1 < dp[i]) {
dp[i] = dp[i - coin] + 1;
usedCoins[i] = coin;
}
}
}
// Reconstruct the solution
std::vector<int> solution;
int currentAmount = amount;
while (currentAmount > 0) {
int coin = usedCoins[currentAmount];
if (coin == -1) return CoinChangeResult(-1, {}); // No solution
solution.push_back(coin);
currentAmount -= coin;
}
return CoinChangeResult(
dp[amount] == INT_MAX ? -1 : dp[amount],
solution
);
}
// Count number of ways to make change
static long long coinChangeWays(const std::vector<int>& coins, int amount) {
std::vector<long long> dp(amount + 1, 0);
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
// Coin change with limited supply
static long long coinChangeLimitedSupply(const std::vector<int>& coins, const std::vector<int>& amounts, int target) {
std::vector<long long> dp(target + 1, 0);
dp[0] = 1;
for (size_t i = 0; i < coins.size(); i++) {
int coin = coins[i];
int maxAmount = amounts[i];
for (int j = target; j >= coin; j--) {
for (int k = 1; k <= maxAmount && k * coin <= j; k++) {
dp[j] += dp[j - k * coin];
}
}
}
return dp[target];
}
// Greedy approach (works only for canonical coin systems)
static int coinChangeGreedy(std::vector<int> coins, int amount) {
// Sort coins in descending order
std::sort(coins.begin(), coins.end(), std::greater<int>());
int remaining = amount;
int coinCount = 0;
for (int coin : coins) {
while (remaining >= coin) {
remaining -= coin;
coinCount++;
}
}
return remaining == 0 ? coinCount : -1;
}
// Coin change with different denominations
struct CoinChangeDenominationResult {
int minCoins;
std::vector<int> denominations;
CoinChangeDenominationResult(int min, const std::vector<int>& d) : minCoins(min), denominations(d) {}
};
static CoinChangeDenominationResult coinChangeDenominations(const std::vector<int>& coins, int amount) {
std::vector<int> dp(amount + 1, INT_MAX);
std::vector<int> denominations(amount + 1, 0);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i && dp[i - coin] != INT_MAX && dp[i - coin] + 1 < dp[i]) {
dp[i] = dp[i - coin] + 1;
denominations[i] = coin;
}
}
}
return CoinChangeDenominationResult(
dp[amount] == INT_MAX ? -1 : dp[amount],
denominations
);
}
// Coin change with fractional coins (knapsack variant)
static double coinChangeFractional(const std::vector<int>& coins, const std::vector<double>& weights, int amount) {
std::vector<double> dp(amount + 1, std::numeric_limits<double>::infinity());
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (size_t j = 0; j < coins.size(); j++) {
int coin = coins[j];
double weight = weights[j];
if (coin <= i) {
dp[i] = std::min(dp[i], dp[i - coin] + weight);
}
}
}
return std::isinf(dp[amount]) ? -1 : dp[amount];
}
// Performance comparison
static void comparePerformance(const std::vector<int>& coins, int amount) {
auto start = std::chrono::high_resolution_clock::now();
int result1 = coinChangeTabulation(coins, amount);
auto end = std::chrono::high_resolution_clock::now();
auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
start = std::chrono::high_resolution_clock::now();
int result2 = coinChangeMemo(coins, amount);
end = std::chrono::high_resolution_clock::now();
auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << "Tabulation: " << result1 << " (" << duration1.count() << " μs)" << std::endl;
std::cout << "Memoization: " << result2 << " (" << duration2.count() << " μs)" << std::endl;
}
};JAVA Implementation
// Coin Change Implementation in Java
// Problem: Find minimum number of coins needed to make amount
import java.util.*;
public class CoinChange {
// Recursive approach (exponential time)
public static int coinChangeRecursive(int[] coins, int amount) {
if (amount == 0) return 0;
if (amount < 0) return -1;
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int result = coinChangeRecursive(coins, amount - coin);
if (result != -1) {
minCoins = Math.min(minCoins, result + 1);
}
}
return minCoins == Integer.MAX_VALUE ? -1 : minCoins;
}
// Top-down DP with memoization
public static int coinChangeMemo(int[] coins, int amount) {
Map<Integer, Integer> memo = new HashMap<>();
return dp(coins, amount, memo);
}
private static int dp(int[] coins, int target, Map<Integer, Integer> memo) {
if (target == 0) return 0;
if (target < 0) return -1;
if (memo.containsKey(target)) return memo.get(target);
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int result = dp(coins, target - coin, memo);
if (result != -1) {
minCoins = Math.min(minCoins, result + 1);
}
}
int result = minCoins == Integer.MAX_VALUE ? -1 : minCoins;
memo.put(target, result);
return result;
}
// Bottom-up DP with tabulation
public static int coinChangeTabulation(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
// Coin change with reconstruction (which coins to use)
public static CoinChangeResult coinChangeWithReconstruction(int[] coins, int amount) {
int[] dp = new int[amount + 1];
int[] usedCoins = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
Arrays.fill(usedCoins, -1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i && dp[i - coin] != Integer.MAX_VALUE && dp[i - coin] + 1 < dp[i]) {
dp[i] = dp[i - coin] + 1;
usedCoins[i] = coin;
}
}
}
// Reconstruct the solution
List<Integer> solution = new ArrayList<>();
int currentAmount = amount;
while (currentAmount > 0) {
int coin = usedCoins[currentAmount];
if (coin == -1) return null; // No solution
solution.add(coin);
currentAmount -= coin;
}
return new CoinChangeResult(
dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount],
solution
);
}
// Count number of ways to make change
public static long coinChangeWays(int[] coins, int amount) {
long[] dp = new long[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
// Coin change with limited supply
public static long coinChangeLimitedSupply(int[] coins, int[] amounts, int target) {
long[] dp = new long[target + 1];
dp[0] = 1;
for (int i = 0; i < coins.length; i++) {
int coin = coins[i];
int maxAmount = amounts[i];
for (int j = target; j >= coin; j--) {
for (int k = 1; k <= maxAmount && k * coin <= j; k++) {
dp[j] += dp[j - k * coin];
}
}
}
return dp[target];
}
// Greedy approach (works only for canonical coin systems)
public static int coinChangeGreedy(int[] coins, int amount) {
// Sort coins in descending order
int[] sortedCoins = coins.clone();
Arrays.sort(sortedCoins);
reverse(sortedCoins);
int remaining = amount;
int coinCount = 0;
for (int coin : sortedCoins) {
while (remaining >= coin) {
remaining -= coin;
coinCount++;
}
}
return remaining == 0 ? coinCount : -1;
}
private static void reverse(int[] arr) {
for (int i = 0; i < arr.length / 2; i++) {
int temp = arr[i];
arr[i] = arr[arr.length - 1 - i];
arr[arr.length - 1 - i] = temp;
}
}
// Coin change with different denominations
public static CoinChangeDenominationResult coinChangeDenominations(int[] coins, int amount) {
int[] dp = new int[amount + 1];
int[] denominations = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i && dp[i - coin] != Integer.MAX_VALUE && dp[i - coin] + 1 < dp[i]) {
dp[i] = dp[i - coin] + 1;
denominations[i] = coin;
}
}
}
return new CoinChangeDenominationResult(
dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount],
denominations
);
}
// Coin change with fractional coins (knapsack variant)
public static double coinChangeFractional(int[] coins, double[] weights, int amount) {
double[] dp = new double[amount + 1];
Arrays.fill(dp, Double.POSITIVE_INFINITY);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
int coin = coins[j];
double weight = weights[j];
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + weight);
}
}
}
return dp[amount] == Double.POSITIVE_INFINITY ? -1 : dp[amount];
}
// Result classes for better organization
public static class CoinChangeResult {
public final int minCoins;
public final List<Integer> coins;
public CoinChangeResult(int minCoins, List<Integer> coins) {
this.minCoins = minCoins;
this.coins = coins;
}
}
public static class CoinChangeDenominationResult {
public final int minCoins;
public final int[] denominations;
public CoinChangeDenominationResult(int minCoins, int[] denominations) {
this.minCoins = minCoins;
this.denominations = denominations;
}
}
}JAVASCRIPT Implementation
// Coin Change Implementation in JavaScript
// Problem: Find minimum number of coins needed to make amount
// Recursive approach (exponential time)
function coinChangeRecursive(coins, amount) {
if (amount === 0) return 0;
if (amount < 0) return -1;
let minCoins = Infinity;
for (let coin of coins) {
const result = coinChangeRecursive(coins, amount - coin);
if (result !== -1) {
minCoins = Math.min(minCoins, result + 1);
}
}
return minCoins === Infinity ? -1 : minCoins;
}
// Top-down DP with memoization
function coinChangeMemo(coins, amount) {
const memo = new Map();
function dp(target) {
if (target === 0) return 0;
if (target < 0) return -1;
if (memo.has(target)) return memo.get(target);
let minCoins = Infinity;
for (let coin of coins) {
const result = dp(target - coin);
if (result !== -1) {
minCoins = Math.min(minCoins, result + 1);
}
}
const result = minCoins === Infinity ? -1 : minCoins;
memo.set(target, result);
return result;
}
return dp(amount);
}
// Bottom-up DP with tabulation
function coinChangeTabulation(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (let coin of coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
// Coin change with reconstruction (which coins to use)
function coinChangeWithReconstruction(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
const usedCoins = new Array(amount + 1).fill(-1);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (let coin of coins) {
if (coin <= i && dp[i - coin] + 1 < dp[i]) {
dp[i] = dp[i - coin] + 1;
usedCoins[i] = coin;
}
}
}
// Reconstruct the solution
const solution = [];
let currentAmount = amount;
while (currentAmount > 0) {
const coin = usedCoins[currentAmount];
if (coin === -1) return null; // No solution
solution.push(coin);
currentAmount -= coin;
}
return {
minCoins: dp[amount] === Infinity ? -1 : dp[amount],
coins: solution
};
}
// Count number of ways to make change
function coinChangeWays(coins, amount) {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (let coin of coins) {
for (let i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
// Coin change with limited supply
function coinChangeLimitedSupply(coins, amounts, target) {
const dp = new Array(target + 1).fill(0);
dp[0] = 1;
for (let i = 0; i < coins.length; i++) {
const coin = coins[i];
const maxAmount = amounts[i];
for (let j = target; j >= coin; j--) {
for (let k = 1; k <= maxAmount && k * coin <= j; k++) {
dp[j] += dp[j - k * coin];
}
}
}
return dp[target];
}
// Greedy approach (works only for canonical coin systems)
function coinChangeGreedy(coins, amount) {
// Sort coins in descending order
const sortedCoins = [...coins].sort((a, b) => b - a);
let remaining = amount;
let coinCount = 0;
for (let coin of sortedCoins) {
while (remaining >= coin) {
remaining -= coin;
coinCount++;
}
}
return remaining === 0 ? coinCount : -1;
}
// Coin change with different denominations
function coinChangeDenominations(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
const denominations = new Array(amount + 1).fill(0);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (let coin of coins) {
if (coin <= i && dp[i - coin] + 1 < dp[i]) {
dp[i] = dp[i - coin] + 1;
denominations[i] = coin;
}
}
}
return {
minCoins: dp[amount] === Infinity ? -1 : dp[amount],
denominations: denominations
};
}
// Coin change with fractional coins (knapsack variant)
function coinChangeFractional(coins, weights, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (let j = 0; j < coins.length; j++) {
const coin = coins[j];
const weight = weights[j];
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + weight);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}PYTHON Implementation
# Coin Change Implementation in Python
# Problem: Find minimum number of coins needed to make amount
def coin_change_recursive(coins, amount):
if amount == 0:
return 0
if amount < 0:
return -1
min_coins = float('inf')
for coin in coins:
result = coin_change_recursive(coins, amount - coin)
if result != -1:
min_coins = min(min_coins, result + 1)
return min_coins if min_coins != float('inf') else -1
# Top-down DP with memoization
def coin_change_memo(coins, amount):
memo = {}
def dp(target):
if target == 0:
return 0
if target < 0:
return -1
if target in memo:
return memo[target]
min_coins = float('inf')
for coin in coins:
result = dp(target - coin)
if result != -1:
min_coins = min(min_coins, result + 1)
result = min_coins if min_coins != float('inf') else -1
memo[target] = result
return result
return dp(amount)
# Bottom-up DP with tabulation
def coin_change_tabulation(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# Coin change with reconstruction (which coins to use)
def coin_change_with_reconstruction(coins, amount):
dp = [float('inf')] * (amount + 1)
used_coins = [-1] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i and dp[i - coin] + 1 < dp[i]:
dp[i] = dp[i - coin] + 1
used_coins[i] = coin
# Reconstruct the solution
solution = []
current_amount = amount
while current_amount > 0:
coin = used_coins[current_amount]
if coin == -1:
return None # No solution
solution.append(coin)
current_amount -= coin
return {
'min_coins': dp[amount] if dp[amount] != float('inf') else -1,
'coins': solution
}
# Count number of ways to make change
def coin_change_ways(coins, amount):
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
# Coin change with limited supply
def coin_change_limited_supply(coins, amounts, target):
dp = [0] * (target + 1)
dp[0] = 1
for i, coin in enumerate(coins):
max_amount = amounts[i]
for j in range(target, coin - 1, -1):
for k in range(1, min(max_amount + 1, j // coin + 1)):
dp[j] += dp[j - k * coin]
return dp[target]
# Greedy approach (works only for canonical coin systems)
def coin_change_greedy(coins, amount):
# Sort coins in descending order
sorted_coins = sorted(coins, reverse=True)
remaining = amount
coin_count = 0
for coin in sorted_coins:
while remaining >= coin:
remaining -= coin
coin_count += 1
return coin_count if remaining == 0 else -1
# Coin change with different denominations
def coin_change_denominations(coins, amount):
dp = [float('inf')] * (amount + 1)
denominations = [0] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i and dp[i - coin] + 1 < dp[i]:
dp[i] = dp[i - coin] + 1
denominations[i] = coin
return {
'min_coins': dp[amount] if dp[amount] != float('inf') else -1,
'denominations': denominations
}
# Coin change with fractional coins (knapsack variant)
def coin_change_fractional(coins, weights, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for j, coin in enumerate(coins):
weight = weights[j]
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + weight)
return dp[amount] if dp[amount] != float('inf') else -1
# Coin change with memoization using decorator
from functools import lru_cache
@lru_cache(maxsize=None)
def coin_change_lru_cache(coins_tuple, amount):
coins = list(coins_tuple)
if amount == 0:
return 0
if amount < 0:
return -1
min_coins = float('inf')
for coin in coins:
result = coin_change_lru_cache(coins_tuple, amount - coin)
if result != -1:
min_coins = min(min_coins, result + 1)
return min_coins if min_coins != float('inf') else -1