Find minimum number of coins that make a given value

December 7, 2021

Find minimum number of coins that make a given value

In Find minimum number of coins that make a given value Problem we have to find minimum number of coins that can sum to the given value.The problem has a dynamic programing solution . In this article , we will provide C++ solution with an explanation.

Find minimum number of coins that make a given value

Find Minimum Number of coins Problem Description

We are given n number of coins each with denomination – C1, C2 … Cn. We are given a sum S. Determine the minimum number of coins required that sum to the given value. Note that we have infinite supply of each coins.

Input

  • First-line contains n and s – the number of coins & the sum.
  • Second-line contains n integers – the denomination of each coin.

Output

  • Single integer the required number of coins.

Problem Solution

The problem can be solved using dynamic programming. The idea is to create a dp table of size S+1 { dp[S+1] }.

dp[i] = minimum number of coins required so that total sum is i.

Now, we have our table defined we need to define dp transitions to calculate newer values from older ones. So to fill dp table for each value of i we will iterate over all possible coins and get the minimum count.

Time Complexity – O(S*n)

Space Complexity – O(S)

Code

#include <bits/stdc++.h>
using namespace std;
int minCoin(int coin[], int n, int s)
{
    int dp[s + 1];

    // Filling large value to mark as not filled
    for (int i = 0; i <= s; i++)
        dp[i] = INT_MAX;

    dp[0] = 0; // FOr 0 sum we need zero coins

    // Getting minimum value for each sum
    for (int sum = 1; sum <= s; sum++)
    {
        for (int c = 0; c < n; c++)
        {
            int coinValue = coin[c];
            // checking all valid coins
            if (sum – coinValue >= 0 && dp[sum – coinValue] != INT_MAX)
            {
                dp[sum] = min(dp[sum], 1 + dp[sum – coinValue]);
            }
        }
    }

    if (dp[s] == INT_MAX)
        return –1;
    return dp[s];
}
int main()
{
    int n, s;
    cin >> n >> s;
    int coin[n];
    for (int i = 0; i < n; i++)
    {
        cin >> coin[i];
    }

    cout << minCoin(coin, n, s) << endl;
    return 0;
}

Output

4 10
2 3 4 5
2

Explanation - 
We need 2 coins of denomination 5.