Application Development, Product to Market
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use

Coin Change Problem

4/3/2018

0 Comments

 
Given coins of different denominations and a total amount of money, find the number of combinations that makes up that amount. ​For example, given unlimited coins in 1, 2, 4 denominations, how many combinations are there to make up the amount of 12?

Thought Process

Given coins in different denominations, we'd solve this problem by breaking it into sub-problems which means given coins in less different denominations. The answer to the problem of given coins in n different denominations is based on solving the problem of given coins in (n-1) different denominations, and the answer to the problem of coins in (n-1) different denominations is based on solving the problem of coins in (n-2) different denominations.

We can use an array named combination to store the number of combinations that make up the amount. For example, the number of combinations to make up the amount of 1 is stored combination[1], and the combinations to make up the amount of 12 is stored in combination [12].

The number of combinations to make up a given amount is equal to the number of combinations before a coin denomination is added to the picture, plus the number of combinations after such a coin denomination is added to the picture for the amount of "amount - coin". 

When adding the first coin to the picture, we'd calculate this array - combination. When adding the 2nd coin to the picture, the same combination[amount] is being calculated based on the following pseudocode:   
Code Editor

    

Read More
0 Comments

    Categories

    All
    Algorithm
    Concurrency
    CQ
    Data Structure
    Design Pattern
    Developer Tool
    Dynamic Programming
    Entrepreneur
    Functional Programming
    IDE
    Java
    JMX
    Marketing
    Marklogic
    Memory
    OSGI
    Performance
    Product
    Product Management
    Security
    Services
    Sling
    Social Media Programming
    Software Development

    Feed Widget

    Archives

    May 2020
    March 2020
    April 2018
    March 2018
    February 2018
    December 2017
    March 2017
    November 2016
    June 2016
    May 2016
    April 2016
    October 2015
    September 2015
    August 2015
    September 2014
    July 2014
    June 2014
    May 2014
    March 2014
    January 2014
    December 2013
    November 2013
    October 2013
    September 2013
    August 2013
    July 2013
    June 2013

    RSS Feed

in loving memory of my mother  and my 4th aunt
Photos used under Creative Commons from net_efekt, schani, visnup, Dan Zen, gadl, bobbigmac, Susana López-Urrutia, jwalsh, Philippe Put, michael pollak, oskay, Creative Tools, Violentz, Kyknoord, mobilyazilar