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

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

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

DominicZA4.1K

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:

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

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.

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.

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

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