How to solve Coin Change problem with amount being a double instead of an int

Question

How would I go about solving a similar problem, in which the amount could be a double value (such as 19.12) instead of strictly an int (such as 19), and the test cases would include dollar bills and coins?

In the typical leetcode problem, I would create a dp array that would store the fewest # of coins to make up whatever amount im currently on. Using bottom-up processing, I would start with the smallest sub-problem (dp[0]=0) and work upto the problem at hand, as seen below:

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for(int i = 0; i <= amount; i++) {
            for(int j = 0; j < coins.length; j++) {
                if(coins[j] <= i) {
                    dp[i] = Math.min(dp[i], 1 + dp[i - coins[j]]);
                }
            }
        }
        return dp[amount] > amount ? - 1 : dp[amount];
    }
}

EDIT

Joni's answer did the trick. Here is my final solution. Basically, the original solution could only read int amounts (whole dollar amounts with 0 cents), but now, the below program separates the double amount into bills and coins and turns both into int values. Then, whatever the original solution was doing, the new one just does the same to both the bills and coins separately. Not sure if that made sense, but here's the solution:

import java.util.Arrays;
import java.util.Scanner;

class Main {
    public static void main (String[] args) {
        int[] billDeno = new int[] {500,200,100,50,20,10,5,2,1};
        int[] coinDeno = new int[] {50,25,10,5,2,1};
        Scanner input = new Scanner(System.in);
        System.out.printf("Enter amount: ");
        double amount = input.nextDouble();
        int y = coinChange(billDeno, coinDeno, amount);
        System.out.println(y);
    }
    
    public static int coinChange(int[] billDeno, int[] coinDeno, double amount) {        
        int numDollars = (int) amount;
        int numCents = (int) ((amount - numDollars) * 100 + 0.5f);
        
        int[] dpDollars = new int[numDollars + 1];
        int[] dpCents = new int[numCents + 1];
        
        Arrays.fill(dpDollars, numDollars + 1);
        Arrays.fill(dpCents, numCents + 1);
        
        dpDollars[0] = 0;
        dpCents[0] = 0;
        
        for(int i = 0; i <= numDollars; i++) {
            for(int j = 0; j < billDeno.length; j++) {
                if(billDeno[j] <= i) {
                    dpDollars[i] = Math.min(dpDollars[i], 1 + dpDollars[i - billDeno[j]]);
                }
            }
        }
        for(int i = 0; i <= numCents; i++) {
            for(int k = 0; k < coinDeno.length; k++) {
                if(coinDeno[k] <= i) {
                    dpCents[i] = Math.min(dpCents[i], 1 + dpCents[i - coinDeno[k]]);
                }
            }
        }
        return dpDollars[numDollars] + dpCents[numCents] > amount ? -1 : dpDollars[numDollars] + dpCents[numCents];
    }
}

This may seem like a hacky solution (especially towards the end), so please feel free to post more optimized solutions. Thanks for all the help!

Answer 1

This will not work with double.

Many decimal fractions such as 0.10 cannot be represented exactly as binary floating point numbers. When you write 0.10 or 0.30 in a Java program, you get the best possible approximation, but not the exact values. See Is floating point math broken?

For example, 0.30 is not three times 0.10. The program will not find a way to make change for 0.3.

What will work is if you multiply the amounts and coin values by 100, so that they are measured in cents, and use int or long. What would also work is using the BigDecimal class instead of double, but then you have to use method calls instead of arithmetic operators.

Answer 2

Now there is a good answer here.

I guess maybe if you would change the int to double it'd work, or maybe not. However it won't go through LeetCode since that's not the desired input/output:

class Solution {
    public double coinChange(double[] coins, double target) {
        if (target < 1)
            return 0;
        return helper(coins, target, new double[target]);
    }

    private double helper(double[] coins, double rem, int[] count) {
        if (rem < 0)
            return -1;
        if (rem == 0)
            return 0;
        if (count[rem - 1] != 0)
            return count[rem - 1];
        int min = Integer.MAX_VALUE;
        for (double coin : coins) {
            double res = helper(coins, rem - coin, count);
            if (res >= 0 && res < min)
                min = 1 + res;
        }

        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];

    }
}

Your input/output should probably look like:

coins = [1.0, 2.0, 5.0, 0.01, 0.1, 0.25, 0.5], amount = 19.12

You'd probably have to debug it, might have some type bugs.

---

For int, this'd pass through LeetCode:

class Solution {
    public int coinChange(int[] coins, int target) {
        if (target < 1)
            return 0;
        return helper(coins, target, new int[target]);
    }

    private int helper(int[] coins, int rem, int[] count) {
        if (rem < 0)
            return -1;
        if (rem == 0)
            return 0;
        if (count[rem - 1] != 0)
            return count[rem - 1];
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = helper(coins, rem - coin, count);
            if (res >= 0 && res < min)
                min = 1 + res;
        }

        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];

    }
}

---

References

• For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2} in there.