[SOLVED] Money Exchange Problem Using C++

Filed Under: C++
Money Exchange Problem Using C

In today’s article, we will learn to solve the money exchange problem using C++. It is a very popular software interview problem. You can expect the top recruiters to ask about this problem during an interview. In this article, we will learn the concept to solve this problem. One can solve this problem using two different strategies, i.e. using the greedy or the dynamic programming approach.

Problem Statement

You have a set of coins of different values. What is the minimum number of coins you would use to change a given value using these coins? Assume that you have an infinite supply of all the coins.

For example,

Coins: [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
Testcase 1: value = 137
Answer: 5

Testcase 2: value = 15
Answer: 2

Testcase 3: value = 7
Answer: 2

Coins: [1, 7, 10]
Testcase 1: value = 14
Answer: 2

Testcase 2: 24
Answer: 3
Example
Example

Concept of the Money Exchange Problem

If you carefully notice, you will find that the greedy approach is not valid for the set: [1, 7, 10]. Hence we would only discuss the dynamic programming solution. Dynamic programming is nothing but optimization of the recursive formulation. We will follow the following instructions while writing the algorithm.

  • The recursive formulation will consider all the possible cases
  • For every case, we have the following recursive relation
    • f(N) = min(f(N - coins[i])), where ‘i’ ranges from 0 to size(coins)
  • It indicates that you can not pick a coin whose value is greater than N
  • As there’s only one variable to determine the total number of states, we will only use a one-dimensional array to store these states
  • The bottom-up approach is as follows.
    • Initialize a dynamic programming array of size N + 1 with INT_MAX
    • To exchange zero, you need not use any coins.
    • Start a for loop, from i = 1 to i = N
      • arr[i] = min(arr[i - coins[j]]), where j varies from j = 0 to j = size(coins)
    • Once you are out of this loop, just return arr[N]

Algorithm to Solve The Money Exchange Problem

int min_coins_bottom_up(vector <int> coins, int N)
{
        int len = coins.size();

        vector <int> dp(N + 1, INT_MAX);

        // to change 0, we need not use
        // any coins
        dp[0] = 0;

        // start filling the array
        // in a bottom-up manner
        for(int i = 1; i <= N; i++)
                for(int j = 0; j < len; j++)
                        if(i - coins[j] >= 0)
                                dp[i] = min(dp[i], dp[i - coins[j]] + 1);

        return dp[N];
}

Solving the Money Exchange Problem Using C++ Progam

Let’s now solve the money exchange problem that we algorithmically understand, using C++.

#include <iostream>
#include <climits>
#include <vector>

using namespace std;

// function to find the minimum number of coins needed
int min_coins_bottom_up(vector <int> coins, int N)
{
        int len = coins.size();

        // initialize the vector for bottom - up approach
        vector <int> dp(N + 1, INT_MAX);

        // to change 0, we need not use
        // any coins
        dp[0] = 0;

        // start filling the array
        // in a bottom-up manner
        for(int i = 1; i <= N; i++)
                for(int j = 0; j < len; j++)
 
                       // only consider the coins whose values
                       // are less than the current state
                        if(i - coins[j] >= 0)
                                dp[i] = min(dp[i], dp[i - coins[j]] + 1);

        // return the answer
        return dp[N];
}

// driver function
int main()
{
        cout << "Enter the coins, press -1 to stop" << endl;

        // array to store the value of coins
        vector <int> coins;

        while(true)
        {
                int ele;
                cin >> ele;

                if(ele == -1)
                        break;

                coins.push_back(ele);
        }

        cout << "Enter the amount to change" << endl;

        int amount;
        cin >> amount;

        cout << "The minimum coins needed to change are: " << min_coins_bottom_up(coins, amount) <<endl;

        return 0;
}
Algorithm
Minimum Coins Algorithm

Output

Minimum Coins Output
Minimum Coins Output

Conclusion

In this article, we learned to solve the money exchange problem using C++. We went through the problem statement, and later we understood the concept. In the end, we coded the algorithm and a driver program to check its working. Notice that for the last case in the output screenshot, the output is INT_MIN. It is so because there’s no possible combination for this particular denomination to make up to eight. That’s it for now, thanks for reading.

Further Readings

To learn more about recursion or dynamic programming, you can go through the following articles,

https://www.journaldev.com/56866/solving-0-n-knapsack-problem-in-cpp

https://www.journaldev.com/56918/0-1-knapsack-using-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content