loading...
Nlogn

DP - Coin Change: Find the number of ways of representing n cents

mayankjoshi profile image mayank joshi Originally published at nlogn.in ・2 min read

interview-question (4 Part Series)

1) Find if a path is possible in a NxM for reaching bottom right form top left 2) Find all possible subset of a given set 3) Print all permutations of a string with unique characters 4) DP - Coin Change: Find the number of ways of representing n cents

Given an infinite supply of 25 cents, 10 cents, 5 cents, and 1 cent. Find the number of ways of representing n cents. (The order doesn't matter).

Ex: n = 10 => {1,1,1,1,1,1,1,1,1,1}
              {1,1,1,1,1,5}
              {5,5}
              {10}

Algorithm:

We are given a set of 4 Coins of type 1 cents, 5 cents, 10 cents, 25 cents. To find the number of ways of making n cents using these 4 cents, we will consider 2 conditions:

  1. Try to make n cents by including the ith cent from the set of 4 coins.      number_of_ways(n-coin_arr[m], coin_arr m);   here m in the number of coins in given set(here m=4).
  2. Try to make n cents by not including the ith cent from the given set of the 4 coins.  number_of_ways(n, coin_arr, m-1);  

This problem involves the repetition of subproblems, so we will use Dynamic Programming.


The number of ways of representing 6 cents using 1cents and 2 cents. (Here for simplicity we have considered a set of 2 coins only)

Implementation of the above code in CPP

  1. Recursive Approach

  2. Iterative Approach

Output

Coins       Output
n = 5 2
n = 26 13
n = 1000 142511




Time Complexity

Since we have used Dynamic Programming here, hence the time complexity of the above program is O(NM), N the total cents to make and M is the number of the coin in a given set.


This post was originally published at nlogn

interview-question (4 Part Series)

1) Find if a path is possible in a NxM for reaching bottom right form top left 2) Find all possible subset of a given set 3) Print all permutations of a string with unique characters 4) DP - Coin Change: Find the number of ways of representing n cents

Posted on Mar 28 by:

mayankjoshi profile

mayank joshi

@mayankjoshi

I love system design and most of the time I find myself learning or designing one of them. I'm highly active on twitter, So ping me there.

Nlogn

nlogn is a Computer Science portal specially designed to help you prepare for product-based companies interviews by practicing a wide variety of problem-related to system Desing, Data-Structure and much more.

Discussion

markdown guide