Algorithms for Coding Interviews in C++/

...

/

Solution: Coin Change Problem

Solution: Coin Change Problem

This review provides a detailed analysis of the different ways to solve The Coin Change Problem

We'll cover the following...

Solution #1: Brute Force

C++
#include <iostream>
using namespace std;
int countChange(int denoms[], int denomsLength, int amount) {
  // If n is 0 then there is 1 solution  
  // (do not include any coin) 
  if (amount == 0)
    return 1;
  // If n is less than 0 then no  
  // solution exists 
  if (amount < 0 || denomsLength <= 0)
    return 0;
  // If there are no coins and n  
  // is greater than 0, then no 
  // solution exist 
  if (denomsLength <= 0 && amount >= 1)
    return 0;
  // count is sum of solutions (i)  
  // including S[m-1] (ii) excluding S[m-1] 
  return countChange(denoms, denomsLength - 1, amount) + countChange(denoms, denomsLength, amount - denoms[denomsLength - 1]);
}
// Driver program to test the functions
int main() {
  // Denominations: quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent)
  int denoms[4] = {25,10,5,1};
  cout << countChange(denoms, 4, 10) << endl;
}

To count the total number of solutions, we divide the solution into two sets:

  1. Solutions that do not contain mth denomination (or denoms[denomsLength-1]).
  2. Solutions that contain at least one denoms[denomsLength-1].

Pseudocode

countChange(denoms[], denomsLength, amount):
    return (countChange(denoms[], denomsLength-1, amount)
   +countChange(denoms[], denomsLength, amount-denoms[denomsLength-1]))

However, notice that the function above recomputes the same subproblem several times.

Time Complexity

The time complexity if this solution is in O(2denomsLength)O(2^{denomsLength}). Why? Because for every coin, we have 2 options: Either include it or exclude it. If we think in terms of binary, it’s 0 to exclude and 1 to include. For example, if we have 2 coins, the options will be 00, 01, 10, 11 which is 4 or 222^2 options. So extrapolating to nn ...