{"id":831,"date":"2024-10-14T14:24:40","date_gmt":"2024-10-14T08:54:40","guid":{"rendered":"https:\/\/codexplained.in\/?p=831"},"modified":"2025-11-24T15:43:14","modified_gmt":"2025-11-24T10:13:14","slug":"given-a-set-of-coin-denominations-and-a-total-amount-find-the-minimum-number-of-coins-needed-to-make-that-amount","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=831","title":{"rendered":"Given a set of coin denominations and a total amount, find the minimum number of coins needed to make that amount."},"content":{"rendered":"\n

Key Concepts<\/h3>\n\n\n\n
    \n
  1. Dynamic Programming<\/strong>: This approach is effective for solving problems where the solution can be composed of solutions to subproblems. Here, we can build up the solution using previously computed results.<\/li>\n\n\n\n
  2. State Representation<\/strong>: We can use a one-dimensional array dp<\/code> where dp[i]<\/code> represents the minimum number of coins needed to make the amount i<\/code>.<\/li>\n<\/ol>\n\n\n\n

    Dynamic Programming Approach<\/h3>\n\n\n\n
      \n
    • Step 1<\/strong>: Initialize an array dp<\/code> of size amount + 1<\/code>, filled with a value larger than the maximum possible coins (like amount + 1<\/code>).<\/li>\n\n\n\n
    • Step 2<\/strong>: Set dp[0] = 0<\/code> because no coins are needed to make zero amount.<\/li>\n\n\n\n
    • Step 3<\/strong>: For each coin denomination, update the dp<\/code> array based on whether including the coin will result in fewer coins needed for each amount.<\/li>\n<\/ul>\n\n\n\n

      C Program for Minimum Coin Change<\/h3>\n\n\n\n

      Here\u2019s a complete C program to solve the Minimum Coin Change problem:<\/p>\n\n\n

      \n#include <stdio.h>\n#include <stdlib.h>\n#include <limits.h>\n\n\/\/ Function to find the minimum number of coins for a given amount\nint minCoins(int coins[], int numCoins, int amount) {\n    \/\/ Create a DP array and initialize it with a high value\n    int* dp = (int*)malloc((amount + 1) * sizeof(int));\n    for (int i = 0; i <= amount; i++) {\n        dp[i] = INT_MAX; \/\/ Initialize to infinity\n    }\n    \n    \/\/ Base case: No coins are needed to make amount 0\n    dp[0] = 0;\n\n    \/\/ Compute minimum coins required for all amounts\n    for (int i = 1; i <= amount; i++) {\n        for (int j = 0; j < numCoins; j++) {\n            if (coins[j] <= i) {\n                if (dp[i - coins[j]] != INT_MAX) {\n                    dp[i] = (dp[i] < dp[i - coins[j]] + 1) ? dp[i] : (dp[i - coins[j]] + 1);\n                }\n            }\n        }\n    }\n\n    \/\/ If dp[amount] is still infinity, return -1\n    int result = (dp[amount] == INT_MAX) ? -1 : dp[amount];\n\n    \/\/ Free the allocated memory\n    free(dp);\n    \n    return result;\n}\n\n\/\/ Main function\nint main() {\n    int numCoins, amount;\n\n    \/\/ Input the number of coins\n    printf("Enter the number of coin denominations: ");\n    scanf("%d", &numCoins);\n\n    int* coins = (int*)malloc(numCoins * sizeof(int));\n\n    \/\/ Input the coin denominations\n    printf("Enter the coin denominations: ");\n    for (int i = 0; i < numCoins; i++) {\n        scanf("%d", &coins[i]);\n    }\n\n    \/\/ Input the total amount\n    printf("Enter the amount to make change for: ");\n    scanf("%d", &amount);\n\n    \/\/ Find the minimum number of coins\n    int minCoinsRequired = minCoins(coins, numCoins, amount);\n    if (minCoinsRequired != -1) {\n        printf("Minimum number of coins needed: %d\\n", minCoinsRequired);\n    } else {\n        printf("It is not possible to make the given amount with the provided denominations.\\n");\n    }\n\n    \/\/ Free the allocated memory\n    free(coins);\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
      Explanation of the Code<\/h3>\n\n\n\n
        \n
      1. Dynamic Programming Table<\/strong>:\n
          \n
        • We create a one-dimensional array dp<\/code> where dp[i]<\/code> stores the minimum number of coins needed to make the amount i<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Filling the DP Array<\/strong>:\n
            \n
          • We initialize the dp<\/code> array to a large value (INT_MAX<\/code>) to represent that those amounts cannot be formed initially.<\/li>\n\n\n\n
          • For each amount from 1<\/code> to amount<\/code>, we check each coin denomination. If the coin can be used (i.e., its value is less than or equal to the current amount), we update the dp[i]<\/code> value.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
          • Final Result<\/strong>:\n
              \n
            • After populating the dp<\/code> array, we check dp[amount]<\/code>. If it is still INT_MAX<\/code>, it means that the amount cannot be formed with the given coins, and we return -1.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • Memory Management<\/strong>:\n
                \n
              • The program dynamically allocates memory for the coins and the dp<\/code> array and frees it at the end to prevent memory leaks.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                Input and Output Example<\/h3>\n\n\n\n
                Input<\/h4>\n\n\n\n
                mathematicaCopy codeEnter the number of coin denominations: 3\nEnter the coin denominations: 1 3 4\nEnter the amount to make change for: 6\n<\/code><\/pre>\n\n\n\n
                Output<\/h4>\n\n\n\n
                typescriptCopy codeMinimum number of coins needed: 2\n<\/code><\/pre>\n\n\n\n
                Explanation of the Output<\/h3>\n\n\n\n
                In this example, the minimum number of coins needed to make the amount 6<\/code> is 2<\/code>, which can be achieved by using two coins of denomination 3<\/code>.<\/p>\n\n\n\n
                Conclusion<\/h3>\n\n\n\n
                This C program efficiently solves the Minimum Coin Change problem using dynamic programming. It allows for user input for flexibility and computes the minimum number of coins required to achieve a given amount with specified denominations. You can test various coin sets and amounts to see how the solution adapts. This approach is widely applicable in financial calculations and resource allocation problems.<\/p>\n