Coin Change with Fewest Number of Coins Given Finite Supply

Problem

You are given an integer array coins representing coins of different denominations and counts representing number of coins available of each denomination and an integer amount representing a total amount of money.

So, to summarise, you are given:

• coins: An integer array representing coins of different denominations.
• counts: An integer array where counts[i] represents the maximum number of coins available for the denomination coins[i].
• amount: An integer representing the total amount of money to form.

The goal is to determine and return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Examples

Example 1:

Input: coins = [1, 2, 5], counts = [5, 2, 1], amount = 11
Output: 3
Explanation: Use 5 + 5 + 1 = 11. Total coins used = 3.

Example 2:

Input: coins = [1, 2, 5], counts = [0, 2, 1], amount = 11
Output: -1
Explanation: It is impossible to form the amount as the coin "1" is unavailable.

Solution

Method 1 - Naive

The naive recursive approach explores all possible combinations of coins to make up the target amount, considering their limited counts. It uses brute force by trying to use 0, 1, ..., counts[i] coins for each denomination recursively.

Approach

1. Base Cases:
   • If amount == 0, return 0 because no coins are needed for 0.
   • If amount < 0 or no coins are left (n == 0), return -1 as it is not possible to form the amount.
2. Recursive Steps:
   • For the current coin coins[n-1] with counts[n-1] available:
     • Try using k coins of this denomination (k from 0 to counts[n-1]).
     • Recursively compute the result for the remaining amount after using k * coins[n-1].
3. Return Minimum:
   • Among all valid ways to form the amount, return the combination with the fewest coins.

Code

C++

class Solution {
public:
    int coinChangeRecursive(vector<int>& coins, vector<int>& counts, int amount) {
        // Helper function for recursion
        function<int(int, int)> helper = [&](int n, int amount) -> int {
            // Base cases
            if (amount == 0) return 0; // No coins needed
            if (n == 0 || amount < 0) return INT_MAX; // Impossible state
            
            int minCoins = INT_MAX;
            for (int k = 0; k <= counts[n - 1]; k++) {
                int remainingAmount = amount - k * coins[n - 1];
                int result = helper(n - 1, remainingAmount);
                if (result != INT_MAX) {
                    minCoins = min(minCoins, result + k);
                }
            }
            
            return minCoins;
        };

        int result = helper(coins.size(), amount);
        return result == INT_MAX ? -1 : result;
    }
};

// Example Usage:
int main() {
    Solution solution;
    vector<int> coins = {1, 2, 5};
    vector<int> counts = {5, 2, 1};
    int amount = 11;
    cout << solution.coinChangeRecursive(coins, counts, amount) << endl;  // Output: 3
}

Java

class Solution {
    public int coinChangeRecursive(int[] coins, int[] counts, int amount) {
        // Recursive helper function
        int helper(int n, int amount) {
            // Base cases
            if (amount == 0) return 0; // No coins needed
            if (n == 0 || amount < 0) return Integer.MAX_VALUE; // Impossible state
            
            int minCoins = Integer.MAX_VALUE;
            for (int k = 0; k <= counts[n - 1]; k++) {
                int remainingAmount = amount - k * coins[n - 1];
                int result = helper(n - 1, remainingAmount);
                if (result != Integer.MAX_VALUE) {
                    minCoins = Math.min(minCoins, result + k);
                }
            }
            
            return minCoins;
        }

        int result = helper(coins.length, amount);
        return result == Integer.MAX_VALUE ? -1 : result;
    }
}

Python

class Solution:
    def coinChangeRecursive(self, coins, counts, amount):
        def helper(n, amount):
            # Base cases
            if amount == 0:
                return 0  # No coins needed
            if n == 0 or amount < 0:  # No denominations or invalid state
                return float('inf')
            
            # Recursive exploration for each count usage (0 to counts[n-1] coins)
            minCoins = float('inf')
            for k in range(0, counts[n - 1] + 1):
                remainingAmount = amount - k * coins[n - 1]
                result = helper(n - 1, remainingAmount)  # Solve subproblem
                if result != float('inf'):  # Valid solution
                    minCoins = min(minCoins, result + k)
            
            return minCoins

        result = helper(len(coins), amount)
        return result if result != float('inf') else -1

# Example Usage:
coins = [1, 2, 5]
counts = [5, 2, 1]
amount = 11
solution = Solution()
print(solution.coinChangeRecursive(coins, counts, amount))  # Output: 3

Complexity

• ⏰ Time complexity: O(n * max_count ^ n) where n is the number of denominations and max_count is the maximum coins available for a single denomination. This is because for each denomination, we recursively explore counts[i] ways for n coins.
• 🧺 Space complexity: O(n). Due to the recursive stack depth corresponding to the number of denominations.

Method 2 - Top-down Dynamic Programming

This approach uses recursion with memoisation to avoid redundant computations and store intermediate results. The memoisation ensures that we solve subproblems only once and reuse the results, significantly optimising the computation compared to the naive recursive approach.

Approach

1. Recursive Function with Memoisation:
   • Define a recursive function dp(n, amount) where:
     • n represents the index of the current denomination we are considering.
     • amount is the remaining amount we need to form.
2. Base Cases:
   • If amount == 0, return 0 (no coins are needed).
   • If amount < 0 or n == 0, return -1 (impossible to form the amount with remaining denominations).
3. Recursive Choices:
   • For each denomination coins[n-1], try using 0, 1, ..., counts[n-1] coins:
     • Calculate the number of coins needed for the remaining amount recursively.
     • Keep track of the minimum number of coins needed across all valid choices.
4. Memoisation:
   • Use a dictionary or array to store the results of (n, amount) subproblems to avoid recomputation.
5. Final Output:
   • Return the result from dp(len(coins), amount) if it is valid; otherwise, return -1.

Code

C++

class Solution {
public:
    int coinChangeTopDown(vector<int>& coins, vector<int>& counts, int amount) {
        // Memoisation map
        unordered_map<string, int> memo;

        function<int(int, int)> dp = [&](int n, int remaining) -> int {
            // Base cases
            if (remaining == 0) return 0; // No coins needed
            if (n == 0 || remaining < 0) return INT_MAX; // Impossible
            
            // Build memoisation key
            string key = to_string(n) + "," + to_string(remaining);
            if (memo.find(key) != memo.end()) return memo[key];
            
            // Recursive computation
            int minCoins = INT_MAX;
            for (int k = 0; k <= counts[n - 1]; k++) {
                int result = dp(n - 1, remaining - k * coins[n - 1]);
                if (result != INT_MAX) {
                    minCoins = min(minCoins, result + k);
                }
            }
            
            // Memoise and return result
            memo[key] = minCoins;
            return minCoins;
        };

        // Solve the problem
        int result = dp(coins.size(), amount);
        return result == INT_MAX ? -1 : result;
    }
};

Example Usage:
int main() {
    Solution solution;
    vector<int> coins = {1, 2, 5};
    vector<int> counts = {5, 2, 1};
    int amount = 11;
    cout << solution.coinChangeTopDown(coins, counts, amount) << endl;  // Output: 3
}

Java

class Solution {
    public int coinChangeTopDown(int[] coins, int[] counts, int amount) {
        // Memoisation map
        Map<String, Integer> memo = new HashMap<>();

        int dp(int n, int remaining) {
            // Base cases
            if (remaining == 0) return 0; // No coins needed
            if (n == 0 || remaining < 0) return Integer.MAX_VALUE; // Impossible
            
            // Build memoisation key
            String key = n + "," + remaining;
            if (memo.containsKey(key)) return memo.get(key);
            
            // Recursive computation
            int minCoins = Integer.MAX_VALUE;
            for (int k = 0; k <= counts[n - 1]; k++) {
                int result = dp(n - 1, remaining - k * coins[n - 1]);
                if (result != Integer.MAX_VALUE) {
                    minCoins = Math.min(minCoins, result + k);
                }
            }
            
            // Memoise and return result
            memo.put(key, minCoins);
            return minCoins;
        }

        // Solve the problem
        int result = dp(coins.length, amount);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] coins = {1, 2, 5};
        int[] counts = {5, 2, 1};
        int amount = 11;
        System.out.println(solution.coinChangeTopDown(coins, counts, amount));  // Output: 3
    }
}

Python

class Solution:
    def coinChangeTopDown(self, coins, counts, amount):
        # Memoisation dictionary
        memo = {}

        def dp(n, remaining):
            # Base cases
            if remaining == 0:
                return 0  # No coins needed
            if n == 0 or remaining < 0:
                return float('inf')  # Impossible to form the amount
            
            # Check memoisation table
            if (n, remaining) in memo:
                return memo[(n, remaining)]
            
            # Minimum number of coins to form 'remaining' using coins[:n]
            minCoins = float('inf')
            for k in range(0, counts[n - 1] + 1):
                result = dp(n - 1, remaining - k * coins[n - 1])
                if result != float('inf'):  # Valid result
                    minCoins = min(minCoins, result + k)
            
            # Store the result in memo table
            memo[(n, remaining)] = minCoins
            return minCoins

        # Solve the problem
        result = dp(len(coins), amount)
        return result if result != float('inf') else -1

# Example Usage:
coins = [1, 2, 5]
counts = [5, 2, 1]
amount = 11
solution = Solution()
print(solution.coinChangeTopDown(coins, counts, amount))  # Output: 3

Complexity

• ⏰ Time complexity: O(n * amount * max_count), where N is the number of denominations, amount is the total target value, and max_count is the maximum count of coins available for any denomination.
• 🧺 Space complexity: O(n * amount). For the memoisation table and recursive stack.

Method 3 - Bottom-up Dynamic Programming

Reasoning or Intuition

1. Dynamic Programming Extension: Instead of considering unlimited coins, we restrict the count of available coins. Each coin denomination has limited availability, necessitating modifications to the standard Knapsack problem. The problem can be addressed using a DP approach by maintaining states for possible amounts and optimising for the fewest coins while verifying constraints on counts.
2. Valid States: For each denomination:
   • Either do not use it, or
   • Use the denomination within its count limit.
3. Final Check: If the amount cannot be formed, return -1.

Approach

1. Initialisation: Create an array dp of size (amount + 1) where dp[i] denotes the minimum coins required to form amount i. Initialise all entries to infinity (float('inf')), except dp[0] = 0, which means no coins are needed for amount 0.
2. Transition: For each denomination coins[i]:
   • Simulate usage of 1 to counts[i] coins of this denomination.
   • Update the DP table (dp[j] = min(dp[j], dp[j - coins[i]] + 1)).
3. Final Output: Return dp[amount] if it is less than infinity; otherwise, return -1.

Code

C++

class Solution {
public:
    int coinChangeWithCounts(vector<int>& coins, vector<int>& counts, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;  // Base case: 0 coins for amount 0

        for (int i = 0; i < coins.size(); i++) {
            int coin = coins[i];
            int maxCount = counts[i];

            // Update DP considering limited coin usage
            for (int j = amount; j >= coin; j--) {
                for (int k = 1; k <= maxCount; k++) {
                    if (j >= k * coin && dp[j - k * coin] != INT_MAX) {
                        dp[j] = min(dp[j], dp[j - k * coin] + k);
                    }
                }
            }
        }

        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

// Example Usage:
int main() {
    Solution solution;
    vector<int> coins = {1, 2, 5};
    vector<int> counts = {5, 2, 1};
    int amount = 11;
    cout << solution.coinChangeWithCounts(coins, counts, amount) << endl;  // Output: 3
}

Java

class Solution {
    public int coinChangeWithCounts(int[] coins, int[] counts, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;  // Base case: 0 coins for amount 0

        for (int i = 0; i < coins.length; i++) {
            int coin = coins[i];
            int maxCount = counts[i];

            // Update DP for limited coin usage
            for (int j = amount; j >= coin; j--) {
                for (int k = 1; k <= maxCount; k++) {
                    if (j >= k * coin && dp[j - k * coin] != Integer.MAX_VALUE) {
                        dp[j] = Math.min(dp[j], dp[j - k * coin] + k);
                    }
                }
            }
        }

        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] coins = {1, 2, 5};
        int[] counts = {5, 2, 1};
        int amount = 11;
        System.out.println(solution.coinChangeWithCounts(coins, counts, amount));  // Output: 3
    }
}

Python

class Solution:
    def coinChangeWithCounts(self, coins, counts, amount):
        # Create DP array
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0  # Base case: 0 coins to make amount 0

        # Iterate over each denomination
        for i in range(len(coins)):
            coin = coins[i]
            max_count = counts[i]
            
            # Track a temporary DP to allow limited use of coins
            for j in range(amount, coin - 1, -1):
                for k in range(1, max_count + 1):
                    if j >= k * coin:
                        dp[j] = min(dp[j], dp[j - k * coin] + k)

        # Return the result
        return dp[amount] if dp[amount] != float('inf') else -1

# Example Usage:
coins = [1, 2, 5]
counts = [5, 2, 1]
amount = 11
solution = Solution()
print(solution.coinChangeWithCounts(coins, counts, amount))  # Output: 3

Complexity

• ⏰ Time complexity: O(n * A * max_count) where n is the number of coin denominations, A is the amount that is the given target, and max_count is the maximum count in the counts array.
• 🧺 Space complexity: O(A), as we use a 1D DP array.