calculate minimum amount of notes needed

Question

0.00/5 (No votes)

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

DominicZA

Add a Solution

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

OriginalGriff · Answer 1 · 2012-11-11T02:48:00

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.

Posted 11-Nov-12 2:48am

OriginalGriff

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.

NKlinkachev · Answer 2 · 2012-11-12T22:02:00

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.