About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career

Coin Change Problem

Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

How To Nail Your Next Tech Interview

Hosted By
Ryan Valles
Founder, Interview Kickstart
Our tried & tested strategy for cracking interviews
How FAANG hiring process works
The 4 areas you must prepare for
How you can accelerate your learnings

Minimum Number of Coins Problem

Given a variety of coin types defining a currency system, find the minimum number of coins required to express a given amount of money. Assume infinite supply of coins of every type. 

Example

Input: Coin types: [1, 3, 5]. Amount to express: 9.

Output: 3

Here are all the unique ways to express 9 as a sum of coins 1, 3 and 5:

1, 1, 1, 1, 1, 1, 1, 1, 1

1, 1, 1, 1, 1, 1, 3

1, 1, 1, 1, 5

1, 1, 1, 3, 3

1, 3, 5

3, 3, 3

Last two ways use the minimal number of coins, 3.

Notes:

Every input will include a coin of value 1. This guarantees that a solution will always exist.

There will be no duplicate coin types in the input.

Constraints:

● 1

● 1

● 1

Solutions

We've provided two solutions.

1) brute_force_solution.cpp

We will follow the following recursive definition:

     If value == 0:

             // Zero coins are required to express the value of 0.

             // End of recursion. Base case.

             return 0

     If value > 0:

             minimum_coins(value) = min {1 + minimum_coins(value-coins[i])} (where i belongs to [0,n-1] and coins[i]

 

Basically what we are doing here is exhaustively searching for all the possible combinations of denominations which can generate our desired value and maintain a minimum number of coins required to generate that value and that will be our answer.

This method is not efficient as it computes subproblems again and again.

Time Complexity:

O(n^value).

Auxiliary Space Used:

O(value). That’s the maximum number of the recursive calls at a time.

Space Complexity:

O(n + value).

Input takes O(n) and the auxiliary space used is O(value).


int minimum_coins(vector &coins, int value) {
    // If value is zero return 0.
    if (value == 0) {
        return 0;
    }
    // Maximum value assigned initially
    int global_min=100005;
    for(int i=0; i < coins.size(); i++){
        if (coins[i] <= value) {
            // To find minimum coins required to make remaining value-coins[i]
            int local_min=minimum_coins(coins, value-coins[i]);
            // local_min number of coins required to make remaining value-coins[i] and 
            // 1 coin with value coins[i] used.
            if (local_min+1 < global_min) {
                global_min=local_min+1;
            }
        }
    }
    // Return maintained global minimum value
    return global_min; 
}


2) optimal_solution.cpp

It is fairly intuitive that the brute force method computes subproblems again and again, so we need to cache the data.

It can be easily done using the bottom-up DP approach. We will use a one-dimensional array as a DP table which at the i-th index stores the minimum number of coins required to value the value i.

Base case: dp[0]=0, other values in the array are set to the positive infinity.

We use 2 loops:

The 1st loop(i) iterates over 1..value.

The 2nd loop(j) iterates over the given coin types.

For every value of i and coins[j] we check if that i (current value to be expressed) is greater than or equals to the coin value, i.e. i>=coins[j]. If yes, then we update dp[i] = min(dp[i],1+dp[i-coins[j]]).

After the dp table has been constructed, dp[value] will

give us our answer.

Time Complexity:

O(n*value).

The outer loop makes value iterations and the inner one makes n iterations.

Auxiliary Space Used:

O(value).

The size of the dp array.

Space Complexity:

O(n + value).

Input takes O(n) and the auxiliary space used is O(value).


const int MAX_VALUE=100005;
int minimum_coins(vector coins, int value) {
    // Dp array of size (value+1) and pre filled value MAX_VALUE
    vector dp(value+1, MAX_VALUE);
    // As number of coins required to make 0 value is 0
    dp[0]=0;
    // Following nested loop calculates the minimum number of coins 
    // required to make the value i and stored in dp table
    int n=coins.size();
    for(int i=1; i <= value; i++) {
        for(int j=0; j < n; j++) {
            if (i >= coins[j] and 1+dp[i-coins[j]] < dp[i]) {
                // Condition that we have found a better minimal solution
                dp[i]=1+dp[i-coins[j]];
            }
        }
    }
    // Recursive function that calculates the distinct combinations of minimal size
    // that has the sum given to the input value
    return dp[value];
}


Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

How To Nail Your Next Tech Interview

Hosted By
Ryan Valles
Founder, Interview Kickstart
Our tried & tested strategy for cracking interviews
How FAANG hiring process works
The 4 areas you must prepare for
How you can accelerate your learnings

Recommended Posts

All Posts