Compute the different ways to make (money) change from $167.37?

Question

This was an interview question:

Given an amount, say $167.37 find all the possible ways of generating the change for this amount using the denominations available in the currency?

Anyone who could think of a space and time efficient algorithm and supporting code, please share.

Here is the code that i wrote (working) . I am trying to find the running time of this, any help is appreciated

    import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;


public class change_generation {

    /**
     * @param args
     */

    public static void generatechange(float amount,LinkedList<Float> denominations,HashMap<Float,Integer> useddenominations)
    {
        if(amount<0)
            return;
        if(amount==0)
        {
            Iterator<Float> it = useddenominations.keySet().iterator();
            while(it.hasNext())
            {
                Float val = it.next();
                System.out.println(val +" :: "+useddenominations.get(val));
            }

            System.out.println("**************************************");
            return;
        }

        for(Float denom : denominations)
        {

            if(amount-denom < 0)
                continue;

            if(useddenominations.get(denom)== null)
                useddenominations.put(denom, 0);

            useddenominations.put(denom, useddenominations.get(denom)+1);
            generatechange(amount-denom, denominations, useddenominations);
            useddenominations.put(denom, useddenominations.get(denom)-1);
        }

    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        float amount = 2.0f;
        float nikle=0.5f;
        float dollar=1.0f;
        float ddollar=2.0f;

        LinkedList<Float> denominations = new LinkedList<Float>();


        denominations.add(ddollar);
        denominations.add(dollar);
        denominations.add(nikle);

        HashMap<Float,Integer> useddenominations = new HashMap<Float,Integer>();
        generatechange(amount, denominations, useddenominations);
    }

}

Hmm, interesting - here's the main article(math-y) - http://en.wikipedia.org/wiki/Change-making_problem and related article - http://en.wikipedia.org/wiki/Greedy_algorithm — Caffeinated, Nov 17 '11 at 23:31
How far have you gotten so far with the question? I would recommend posting what you have, since improving something already there is easier thank making answers from scratch. — ford, Nov 17 '11 at 23:32
@ ford : I couldnt reach far as there was not much time, all i could say was this could be solved recursively, each time subtracting the value of the denomination that you decide to use... — Nohsib, Nov 17 '11 at 23:34
Duplicate: http://stackoverflow.com/questions/1106929/find-all-combinations-of-coins-when-given-some-dollar-value — Deltik, Nov 17 '11 at 23:37
@ Deltik : yes it is, but i dont see an answer accepted in that thread.. — Nohsib, Nov 17 '11 at 23:48
A little bit of *research* goes a long way to writing a better question -1. — , Nov 17 '11 at 23:51
In the context of an interview I would go with a recursive solution because it is easier (for me at least) to conceptualize. Spend more time selling yourself and less time programming. — emory, Nov 18 '11 at 00:36

score 4 · Answer 1 · edited May 23 '17 at 12:27

4

EDIT

This is a specific example of the combination / subset problem, answered here.

Finding all possible combinations of numbers to reach a given sum

--- I am retaining my answer below (as it was usefull to someone), however, admittedly, it is not a direct answer to this question ---

ORIGINAL ANSWER

The most common solution is dynamic programming :

First, you find the simplest way to make change of 1, then you use that solution to make change for 2, 3, 4, 5, 6, etc.... At each iteration, you "check" if you can go "backwards" and decrease the amount of coins in your answer. For example, up to "4" you must add pennies. But, once you get to "5", you can remove all pennies, and your solution has only one coin required : the nickel. But then, until 9, you again must add pennies, etc etc etc.

However, the dynamic programming methodology is not gauranteed to be fast.

Alternatively, you can use a greedy method, where you continually pick the largest coin possible. This is extremely fast , but doesnt always give you an optimal solution. However, if your coins are 1 5 10 and 25 , Greedy works perfectly, and is much faster then the linear programming method.

edited May 23 '17 at 12:27

Community

1
1

answered Nov 17 '11 at 23:39

jayunit100

17,388
22
92
167

3

Nohsib wants to generate all possible ways, not find the optimal way. – Piotr Praszmo Nov 17 '11 at 23:59
In the context of the problem (find all the possible ways of generating the change) what is an optimal solution? It seems there is only one correct solution to this problem. – emory Nov 18 '11 at 00:00
the problem was to get all the possibilities and not the optimal one – Nohsib Nov 18 '11 at 00:02
@Banthar: when you back-trace the table that you create while solving the subset sum problem with dynamic programming, at every its cell you may have multiple options that will fork the path. These options are: (1) sum=this cell's number, (2) sum=some other number(s) from other cell(s), (3) sum=this cell's number+some other number(s) from other cell(s). You may have a combination of (1)+(2) or (2)+(3). If you navigate all possible paths from each cell, you'll have all possible solutions. – Alexey Frunze Nov 18 '11 at 03:32

score 2 · Answer 2 · answered Nov 18 '11 at 01:35

Memoization (kind of) is your friend here. A simple implementation in C:

unsigned int findRes(int n)
{
   //Setup array, etc.

   //Only one way to make zero... no coins.
   results[0] = 1;

   for(i=0; i<number_of_coins; i++)
   {
       for(j=coins[i]; j<=n; j++)
       {
           results[j] += results[j - coins[i]];
       }
   }

   return results[n];
}

So, what we're really doing here is saying:

1) Our only possible way to make 0 coins is 0 (this is our base case)

2) If we are trying to calculate value m, then let's check each coin k. As long as k <= m, we can use that coin k in a solution

3) Well, if we can use k in a solution, then couldn't we just take the solution for (m-k) and add it to our current total?

am i missing something or does this solution only allow using each coin up to 1 time? — Jordan Sitkin, Oct 14 '12 at 16:42

score 0 · Answer 3 · answered Nov 17 '11 at 23:48

I'd try to model this in real life.

If you were at the till and you knew you had to find $167.37 you would probably initially consider $200 as the "simplest" tender, being just two notes. Then, if I had it, I may consider $170, i.e. $100, $50 and $20 (three notes). See where I am going?

More formally, try to over-tender with the minimum number of notes/coins. This would be much easier to enumerate than the full set of possibilities.

score 0 · Answer 4 · answered Nov 18 '11 at 00:37

Don't use floats, even tiniest inaccuracies will destroy your algorithm.

Go from biggest to lowest coin/banknote. For every possible amount call the function recursively. When there are no more coins left pay the rest in ones and print the solution. This is how it looks in pseudo-C:

#define N 14

int coinValue[N]={20000,10000,5000,2000,1000,500,200,100,50,20,10,5,2,1};
int coinCount[N];

void f(int toSpend, int i)
{

    if(coinValue[i]>1)
    {
        for(coinCount[i]=0;coinCount[i]*coinValue[i]<=toSpend;coinCount[i]++)
        {
            f(toSpend-coinCount[i]*coinValue[i],i+1);
        }
    }
    else
    {
        coinCount[i]=toSpend;
        print(coinCount);
    }

}

@ Banthar : any idea as whats wrong with what i have written/ — Nohsib, Nov 18 '11 at 00:43

score 0 · Accepted Answer · edited Apr 24 '13 at 02:28

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;

public class change_generation {

  static int jj=1;

  public static void generatechange(float amount,LinkedList<Float> denominations, 
                                  HashMap<Float,Integer> useddenominations) {
    if(amount<0)
        return;
    if(amount==0) {
        Iterator<Float> it = useddenominations.keySet().iterator();
        while(it.hasNext()) {
            Float val = it.next();
            System.out.println(val +" :: "+useddenominations.get(val));
        }
        System.out.println("**************************************");

        return;
    }

    for(Float denom : denominations) {
        if(amount-denom < 0)
            continue;
        if(useddenominations.get(denom)== null)
            useddenominations.put(denom, 0);

        useddenominations.put(denom, useddenominations.get(denom)+1);
        generatechange(amount-denom, denominations, useddenominations);
        useddenominations.put(denom, useddenominations.get(denom)-1);
    }
  }

  public static void main(String[] args) {
    float amount = 2.0f;
    float nikle=0.25f;
    float dollar=1.0f;
    float ddollar=2.0f;

    LinkedList<Float> denominations = new LinkedList<Float>();

    denominations.add(ddollar);
    denominations.add(dollar);
    denominations.add(nikle);

    HashMap<Float,Integer> useddenominations = new HashMap<Float,Integer>();
    generatechange(amount, denominations, useddenominations);
  }
}

Compute the different ways to make (money) change from $167.37?

5 Answers5

Linked