Is a single loop with several statements and conditions better than several simple loops?

Question

I was creating a very simple program that determines how many coins you need to return the change to a client, using a greedy algorithm. The algorithm is really obvious, you just need to determine which is the bigger coin you can use, subtract its value from the change and update the coins counter.

I have thought of two really similar implementations.

note: changeInt is the change, multiplied by 100 and converted into a integer.

1) A single "complex" loop

while(changeInt != 0) {
       if(changeInt - 25 >= 0){
           changeInt -= 25;
           coins++;
       }
       else if(changeInt - 10 >= 0){
           changeInt -= 10;
           coins++;
       }
       else if(changeInt - 5 >= 0){
           changeInt -= 5;
           coins++;
       }
       else if(changeInt - 1 >= 0){
           changeInt -= 1;
           coins++;
       }

   }

2) Multiple simple loops

    while(changeInt - 25 >= 0) 
   {
       changeInt -= 25;
       coins++;
   }
    while(changeInt - 10 >= 0)
   {
       changeInt -= 10;
       coins++;
   }

    while(changeInt - 5 >= 0)
   {
       changeInt -= 5;
       coins++;
   }

    while(changeInt - 1 >= 0)
   {
       changeInt -= 1;
       coins++;
   }

Now, I know the performance will probably be similar in both cases, since the algorithm is the same, but I was wondering which approach is better.

The single loop is the first idea I came up with, then I thought of the second method and it intuitively seems better to me.

I don't really care about my exact scenario, I'm more interested in the general one (several simple loops vs few more complex loops)

1) Which approach is better in terms of performance?

2) Is the difference noticeable, at least when working with huge numbers?

3) Is one approach significantly more readable than the other? (not sure if I can ask that here)

Thank you!

Answer 1

As others have mentioned, the second approach is preferable since it uses less comparisons.

A cleaner, more concise way would be to use division and modulus:

int current = changeInt;
coins += current / 25;
current %= 25;
coins += current / 10;
current %= 10;
coins += current / 5;
current %= 5;
coins += current;

While the div and mod operators are more expensive than subtracting, it's likely to be faster for larger value of changeInt and there are no branches.

Answer 2

If you had to choose between the looped approaches you described, the second would be preferable (with a slight variation). It is cleaner, and mostly avoids unnecessary testing.

Here's the slight variation ...

while(changeInt >= 25) {
   changeInt -= 25;
   coins++;
}

while(changeInt >= 10) {
   changeInt -= 10;
   coins++;
}

while(changeInt >= 5) {
   changeInt -= 5;
   coins++;
}

while(changeInt > 0) {
   changeInt -= 1;
   coins++;
}

The primary advantage that this offers is that it helps ensure that 'changeInt - X' never wraps around. From what you described in your post, it is unlikely that it would be an issue, but if the type were change from a signed integer to an unsigned integer, then you might have found yourself trying to figure out where the bug lay.

Alternatively, you may wish to use a combination of the division and modulus operators to calculate the change and avoid the loops.

Hope this helps.