12,827,730 members (44,583 online)
Rate this:
See more:
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.

Dom
Posted 11-Nov-12 3:29am
DominicZA4.1K

Rate this:

## 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.
Rate this:

## 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.

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 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!

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.

Top Experts
Last 24hrsThis month
 OriginalGriff 315 Dave Kreskowiak 110 F-ES Sitecore 95 Member 12986391 85 Jochen Arndt 83
 OriginalGriff 5,622 Graeme_Grant 3,935 Karthik Bangalore 3,706 ppolymorphe 2,799 Jochen Arndt 2,739