Strange counting behavior in simple change making program

Question

So I was making this fairly straight forward optimal change program that works perfectly fine in most cases. But for some odd reason it acts inconsistent and sometimes won't add the last penny needed, but other times it will.

I've tried different outputs and the code always comes out correct except sometimes for the last penny; when using American currency. I'm sure the reason is obvious, but I just don't see it.

   public static int[] optimal_change(double[] currency, double amount) {

        int[] count = new int[currency.length];

        for (int i = 0; i < currency.length; i++) {
            if (amount >= currency[i]) {
                amount -= currency[i];
                count[i]++;
                i--;
            }
            if (amount == 0.0000) {
                break;
            }
        }

        return count;
    }

public static void main(String[] args) {

        double[] american_currency = {100,50,20,10,5,1,0.25,0.10,0.05,0.01};
        //Japanese currency: https://www.boj.or.jp/en/note_tfjgs/note/valid/index.htm/
        double[] japanese_currency = {10000,5000,2000,1000,500,100,50,10,5,1};

        int[] american_change = optimal_change(american_currency, 78.36);
        int[] japanese_change = optimal_change(japanese_currency, 793048);

        System.out.println("Optimal change for: $78.38");
        for (int i = 0; i < american_currency.length; i++) {
            if (i <= 5) {
                System.out.println(Integer.toString(american_change[i]) + " $" + Double.toString(american_currency[i]));
            } else {
                System.out.println(Integer.toString(american_change[i]) + " " + Double.toString(american_currency[i]) + "¢");
            }
        }
        System.out.println("--------------------------");
        System.out.println("Optimal change for: ¥793040");
        for (int i = 0; i < japanese_currency.length; i++) {

            System.out.println(Integer.toString(japanese_change[i]) + " ¥" + Double.toString(japanese_currency[i]));

        }


    }

Correct Results:

input: 78.37

output:

Optimal change for: $78.37

0 $100.0

1 $50.0

1 $20.0

0 $10.0

1 $5.0

3 $1.0

1 0.25¢

1 0.1¢

0 0.05¢

2 0.01¢

Incorrect Results:

input: 78.38

output:

Optimal change for: $78.38

0 $100.0

1 $50.0

1 $20.0

0 $10.0

1 $5.0

3 $1.0

1 0.25¢

1 0.1¢

0 0.05¢

2 0.01¢

The output Should have been:

Optimal change for: $78.38

0 $100.0

1 $50.0

1 $20.0

0 $10.0

1 $5.0

3 $1.0

1 0.25¢

1 0.1¢

0 0.05¢

3 0.01¢

Don’t use doubles when an exact answer is required. See chapter "Avoid float and double if exact answers are required" in "Effective Java". (item 48 here: http://the-eye.eu/public/Books/IT%20Various/Effective%20Java%2C%202nd%20Edition.pdf) — , Apr 17 '19 at 07:23
I strongly suspect this is because you are using `double` to represent currency. That has significant problems, because currency is naturally *decimal*, and not all decimal values can be exactly represented in binary floating point. For example, the value 0.1 can't be represented exactly. Options: 1) use integers, representing the number of cents (etc) rather than dollars. 2) use BigDecimal which is a decimal-based floating point type. — Jon Skeet, Apr 17 '19 at 07:23

score 0 · Accepted Answer · answered Apr 18 '19 at 00:39

Switching To BigDecimal seemed to fix the issue. Not sure why the issue with doubles has persisted this long. But thankfully it works.

import java.math.BigDecimal;

public class Greedy_Money_BigInteger {
    public static int[] optimal_change(BigDecimal[] currency, BigDecimal amount) {

        int[] count = new int[currency.length];

        for (int i = 0; i < currency.length; i++) {
            //if (amount >= currency[i]) {
            if (amount.compareTo(currency[i]) >= 0) {
                amount = amount.subtract(currency[i]);
                count[i]++;
                i--;
            }
            if (amount.compareTo(BigDecimal.valueOf(0)) <= 0) {
                break;
            }
        }

        return count;
    }


    public static void main(String[] args) {

        BigDecimal[] american_currency = {BigDecimal.valueOf(100),BigDecimal.valueOf(50),BigDecimal.valueOf(20),BigDecimal.valueOf(10),BigDecimal.valueOf(5),BigDecimal.valueOf(1),BigDecimal.valueOf(0.25),BigDecimal.valueOf(0.10),BigDecimal.valueOf(0.05),BigDecimal.valueOf(0.01)};
        //Japanese currency: https://www.boj.or.jp/en/note_tfjgs/note/valid/index.htm/
        BigDecimal[] japanese_currency = {BigDecimal.valueOf(10000),BigDecimal.valueOf(5000),BigDecimal.valueOf(2000),BigDecimal.valueOf(1000),BigDecimal.valueOf(500),BigDecimal.valueOf(100),BigDecimal.valueOf(50),BigDecimal.valueOf(10),BigDecimal.valueOf(5),BigDecimal.valueOf(1)};

        BigDecimal american_change_value = BigDecimal.valueOf(78.31);
        BigDecimal japanese_change_value = BigDecimal.valueOf(793043);

        int[] american_change = optimal_change(american_currency, american_change_value);
        int[] japanese_change = optimal_change(japanese_currency, japanese_change_value);

        System.out.println("Optimal change for: $" + american_change_value.toString());
        for (int i = 0; i < american_currency.length; i++) {
            if (american_change[i] > 0) {
                if (i <= 5) {
                    System.out.println(Integer.toString(american_change[i]) + " $" + american_currency[i].toString());
                } else {
                    System.out.println(Integer.toString(american_change[i]) + " " + american_currency[i].toString() + "¢");
                }
            }
        }
        System.out.println("--------------------------");
        System.out.println("Optimal change for: ¥" + japanese_change_value.toString());
        for (int i = 0; i < japanese_currency.length; i++) {
            if (japanese_change[i] > 0) {
                System.out.println(Integer.toString(japanese_change[i]) + " ¥" + japanese_currency[i].toString());
            }
        }


    }
}

score -1 · Answer 2 · answered Apr 17 '19 at 07:40

-1

As pointed out by other people in the comments, the problem is caused by Java “approximation” of the values of a double.

Change it in BigDecimal.

Refer to this question for additional information.

answered Apr 17 '19 at 07:40

Capo80

46
3

Strange counting behavior in simple change making program

2 Answers2