Databases
StackOverflow2013
Postsdbo
POCompute the different ways to make (money) change from $167.37?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POCompute the different ways to make (money) change from $167.37?
    text
    copied!<p>This was an interview question:</p> <blockquote> <p>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?</p> </blockquote> <p>Anyone who could think of a space and time efficient algorithm and supporting code, please share.</p> <p><strong>Here is the code that i wrote (working) . I am trying to find the running time of this, any help is appreciated</strong></p> <pre><code> 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&lt;Float&gt; denominations,HashMap&lt;Float,Integer&gt; useddenominations) { if(amount&lt;0) return; if(amount==0) { Iterator&lt;Float&gt; 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 &lt; 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&lt;Float&gt; denominations = new LinkedList&lt;Float&gt;(); denominations.add(ddollar); denominations.add(dollar); denominations.add(nikle); HashMap&lt;Float,Integer&gt; useddenominations = new HashMap&lt;Float,Integer&gt;(); generatechange(amount, denominations, useddenominations); } } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload