Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach
3.
Approach-1 
3.1.
Complexity Analysis
4.
Approach-2
4.1.
Complexity Analysis
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

Coin Change Problem C++

Author Akash Nagpal
0 upvote

Introduction

The coin Change problem is the most asked interview question and is an example of dynamic programming.

Now let us understand the problem statement.

Problem Statement

Given ‘N’ as the number of coins and an array containing some integers (say coins[]) (coins in rupees). The array contains various coins where ‘N’ is a coin. The objective is to change the number of coins ‘N’ using the coins in the array. Make a change that uses the minimum number of coins possible.

 

Example-1

Let us take input array coins[] = {10, 25, 5}

total coins = 3

Also, we have N = 30

The output will be 2

Therefore, A 25 rupee coin and a 5 rupee coin gives us N=30. (25 + 5 = 30)

 

Example-2

coins[] = {3, 9, 5, 5}, total coins = 4

N = 13

The output will be 3 

We will use two 5 rupees coins and one 1 rupee coin. (5 + 5 + 3 = 13)

 

Approach

This problem can be solved using two approaches: 

  • Using Recursion
  • Using bottom-up dynamic programming.

Approach-1 

A recursive method is used in this approach.

  • We start with N and divide the problem into smaller subproblems with each iteration. 
  • This is accomplished by subtracting N from each coin in the coins array. 
  • The scenario in which N equals 0 provides the desired solution. 
  • We return the smallest of all possible combinations as an ideal solution.

 

C++ Code

#include <bits/stdc++.h>  
using namespace std;  
  
// initializing coins array 
int coins[] = { 10, 25, 5 }; 
// array for memoization technique
int dp[1000] = { 0 }; 


// Here, N is sum and M is total_coins 
int minCoins(int N, int M)  
{  
  
    for (int i = 0; i <= N; i++)
    {  
        // Initializing all dp[] value to INT_MAX
        dp[i] = INT_MAX;  
    }
// Base case if sum = zero means rupees = 0
    dp[0] = 0;  
  
    // outer loop denotes possible values of sum between 1 to N  
    for (int i = 1; i <= N; i++) {  
        //Inner loop denotes index of coin array.   
        for (int j = 0; j < M; j++) {    
            if (coins[j] <= i) {  
                //Solution might have the newly added coin  
                dp[i] = min(dp[i], 1 + dp[i - coins[j]]);  
            }  
        }  
    }  
    return dp[N];  
}  
  
int main()  
{  
  
    int sum = 30; 
    int total_coins = 3; 
    cout << "Minimum number of coins needed are " << minCoins(sum, total_coins);  
}  
You can also try this code with Online C++ Compiler
Run Code

Output

Minimum number of coins needed are 2
You can also try this code with Online C++ Compiler
Run Code

Complexity Analysis

  • Time Complexity: O(2^N)
  • Space Complexity: O(2^N)

Note: The above approach does not work efficiently for more large inputs. Therefore, The recursive technique fails in this example.

Try and compile by yourself with the help of online C++ Compiler for better understanding.

Check out Longest Common Substring

Approach-2

This method is based on the concept of bottom-up dynamic programming.

  • There is a condition of overlapping subproblems because subproblems are computed repeatedly. 
  • The problem of recomputation can be overcome by applying the memoization property, that is, by creating a dp[] array that keeps the computed values at a specific stage. 
  • Calculate all potential combinations at each level. 
  • The last value in the dp[] array provides the answer after all the combinations.

 

C++ Code

#include <bits/stdc++.h>  
using namespace std;  
  
// initializing the coins array  
int coins[] = { 10, 25, 5 }; 
// array for memoization  
int dp[1000] = { 0 }; 
int minCoins(int N, int M)    // N = sum and M = total coins  
{  
  
    for (int i = 0; i <= N; i++)  
        dp[i] = INT_MAX; // Initialising all dp[] elements to INT_MAX  
  
        dp[0] = 0; // Base case if sum = 0
  
     //Iterating in outer loop for all the possible sum values    
    for (int i = 1; i <= N; i++) {  
        //Inner loop denotes the index of coin array.   
        for (int j = 0; j < M; j++) {   
            if (coins[j] <= i) {  
                //Solution might include the newly added coins 
                dp[i] = min(dp[i], 1 + dp[i - coins[j]]);  
            }  
        }  
    }  
    return dp[N];  
}  
  
int main()  
{  
  
    int sum = 30;   
    int total_coins = 3;  
    cout << "Minimum coins needed are " << minCoins(sum, total_coins);  
}  
You can also try this code with Online C++ Compiler
Run Code

Output

Minimum coins needed are 2
You can also try this code with Online C++ Compiler
Run Code

Complexity Analysis

  • Time Complexity: The time complexity of the above code is O(total_coins * sum) ≈ O(N2). Since the outcomes from each step are saved and reused in subsequent cycles, this is a far more efficient technique.
  • Space Complexity: The space complexity for the above code will be O(N2) due to the auxiliary space used in the program.  

Since the outcomes from each step are saved and reused in subsequent cycles, this is a far more efficient technique.

Check out this problem - Minimum Coin Change Problem 

Must Read Julia Programming Language

FAQs

  1. What is bottom-up dynamic programming?
    The bottom-up technique (to dynamic programming) evaluates the “smaller” subproblems first, then solves the bigger subproblems using the solutions to the smaller ones.
  2. What do you mean by memoization in dynamic programming?
    Memoization is a recursive algorithm performance improvement method. It involves changing the recursive algorithm to store answers to problems in an array as they are discovered. Instead of needing to recalculate results, recursive calls may search them up in the array. Since partial results are never computed twice, memorization boosts performance, for example, the Fibonacci series.

Key Takeaways

This article extensively discussed the Coin Change Problem in C++. The article explains the different approaches used to solve the problem. There are many more approaches, but these are the most efficient in terms of time and space.

Recommended Readings:

We hope that this blog has helped you enhance your knowledge regarding dynamic programming and recursion using this article and if you would like to learn more, check out our articles on Coding Ninjas. Do upvote our blog to help other ninjas grow. 

Happy Coding!

Live masterclass