AntInLoop

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