Optimal change with only with two euros coins and five and ten euros bills

Question

We assume we have unlimited number of coins and bills. My code works fine but the method optimalChange() has a Cyclomatic Complexity of 8.

import java.util.*;
import java.math.*;

class Change {
   long coin2 = 0;
   long bill5 = 0;
   long bill10 = 0;
}

class Solution {

  static Change optimalChange(long s) {
    long change = s;
    Change c = new Change();
    if (change >=10) {
        if (change % 2 != 0 && change % 5 !=0) {
            return dealWithChangeLike31Euros(change);
        }
        else {
            c.bill10 = (long) change / 10;
            change = change % c.bill10;
        }
    }

    if (change <10 && change >=5) {
        if (change % 2 == 0) {
            c.bill5 = 0;
            c.coin2 = change/2;
        }
        else {
            change = change - 5;
            c.bill5 = 1;
        }
    }

    else if (change %2 ==0) {
        c.bill5 = 0;
        c.coin2 = change/2;
    } else {
        return null;
    }
    return c;
  }

  static Change dealWithChangeLike31Euros(long s) {
    Change c = new Change();
    c.bill10 = ((long) s / 10) - 1;
    long change = (long) s % (c.bill10 * 10);
    if (change > 5) {
        change = change - 5;
        c.bill5 = 1;
    }
    if (change % 2 == 0) {
        c.coin2 = change / 2;
    }
    else {
        return null;
    }
    return c;
  }
}

Can the implementation of the dealWithChangeLike31Euros() method be merged into the other method?

Answer 1

The only way of making an odd total is with a five euro bill. There is no point ever having more than 1 five euro bill, as you could replace pairs with a ten euro bill. So, you should start off checking for the odd total.

if (change >= 5  &&  change % 2 == 1) {
    c.bill5 = 1;
    change -= 5;
}

At this point, you can simply compute the number of ten euro bills, and remaining 2 euro coins.

c.bill10 = change / 10;
change = change % 10;

c.coin2 = change / 2;

The only thing you have to watch out for is a total change amount of 1 or 3 euros (or negative), which is not possible to make. Handle those as a special case.

---

Your optimalChange() creates a change object, and if dealWithChangeLike31Euros() methods is called, it creates its own Change object, and the first object is abandoned. You shouldn't create the object if it isn't going to be used. Options include passing the change object to the dealWithChangeLike31Euros() method, or delaying the creation.

Multiple return points is sometimes a code smell. optimalChange() has 3:

• return dealWithChangeLike31Euros(change);
• return null;
• return c;

If you initialized Change c = null;, and only created the Change object when needed, you could have just the one return c; at the end. Less returns may reduce the complexity.