Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
I am trying to write an algorithm that calculates the minimum number of "notes", or currency needed to get to a value.
 
The most obvious way is to just say:
var notes = [];
while (val != 0) {
    //loop through array of possible notes
    for (note in noteArray) {
        if (note >= val) {
           notes.push(note);
           val -= note;
        }    
    }
}
 
This works 100%, except that now I am doing it on a mobile device, it has a noticeable lag before it draws the result. Is there a quicker algorithm out there for achieving this?
 
I was thinking about implementing a binary chop into it and seeing if it made a difference.
 
Thanks in advance,
Dom
Posted 11-Nov-12 2:29am
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

Assuming that your note array in ordered largest first, I would simply divide the value by each note value in turn: the quotent is the number of those notes to issue, the remainder gets passed down to the next note denomination.
 
So if your value is 123 and your notes are 10, 5, and 1:
123 / 10: Q == 12, R == 3  (12 x 10 notes)
  3 /  5: Q ==  0, R == 3  (no 5 notes)
  3 /  1: Q ==  3, R == 0  (3 x 1 notes)
Only one loop is required.
  Permalink  
Comments
NKlinkachev at 13-Nov-12 3:47am
   
Just to add that while this algorithm might work for currencies and notes as their values are designed in such a way that you can get the value of the next higher note using lower value notes, it is not always the case. Consider the case where you want to get value 9 using notes only of 7 and 3. If your input is real life currency values then this is the best and fastest solution. If you want to handle all cases then a search algorithm is needed ( just a simple recursion, nothing too complicated). See my solution for the recursive algorithm.
OriginalGriff at 13-Nov-12 3:56am
   
I would agree - but the OP was effectively using this algorithm already, and just needed to be shown a quicker way to achieve the same thing. But it's a good point!
NKlinkachev at 13-Nov-12 4:06am
   
Just making sure he is doing the right thing because when I first came across this problem I used currencies and notes to describe it when asking but in fact had to solve it in the general case, not realizing currency values are a special case.
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 2

For real life currencies and notes: their values are designed in such a way that you can get the value of the next higher note using lower value notes so Solution 1 is the best one in this case. It is not always the case however for any combination of note values. Consider the case where you want to get value 9 using notes only of 7 and 3.
 
This algorithm handles all cases of note values and final value;
It's just a pseudocode.
Assuming your notes are ordered from highest to lowest value.
 
solve( v - value, ind - current note value index) {
if (v==0) SOLUTION FOUND
if (ind == max_ind) LOWEST NOTE REACHED, NO SOLUTION IN THAT BRANCH OF THE RECURSION
integer mcn = v % Notes[ind]; // max number of current notes
for (i = mcn to 0) {
use i notes of value Notes[ind]: v-=i*Notes[ind]
 
check if solution exist: solve(v,ind+1)
 
"unuse" i notes of value Notes[ind]: v+=i*Notes[ind]
}
}
 
Hope this helps. If you have any questions feel free to ask.
  Permalink  

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
0 OriginalGriff 310
1 PhilLenoir 164
2 Richard MacCutchan 160
3 Sharmanuj 146
4 Magic Wonder 129
0 Sergey Alexandrovich Kryukov 6,081
1 OriginalGriff 5,115
2 CPallini 2,473
3 Richard MacCutchan 1,597
4 Abhinav S 1,505


Advertise | Privacy | Mobile
Web02 | 2.8.140814.1 | Last Updated 13 Nov 2012
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100