12,881,797 members (29,289 online)
Rate this:
Please Sign up or sign in to vote.
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.

Thanks in advance,
Dom
Posted 11-Nov-12 2:29am
DominicZA4.1K

## 2 solutions

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

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

Top Experts
Last 24hrsThis month
 OriginalGriff 245 bling 95 Afzaal Ahmad Zeeshan 95 ppolymorphe 80 Kornfeld Eliyahu Peter 40
 OriginalGriff 3,747 Karthik Bangalore 2,391 CHill60 2,358 Jochen Arndt 1,998 ppolymorphe 1,800

Advertise | Privacy | Mobile
Web02 | 2.8.170422.1 | Last Updated 13 Nov 2012
Copyright © CodeProject, 1999-2017
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