Solve Decimal Coin Change
Company: Snapchat
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a list of coin denominations represented as decimal values and a target amount represented as a decimal value, return the minimum number of coins needed to sum exactly to the target. You may use each denomination an unlimited number of times.
If the target cannot be formed exactly, return `-1`.
The input decimals may include values such as `0.25`, `0.50`, and `1.00`. You must handle floating-point precision safely.
Example:
```text
denominations = [0.25, 0.50, 1.00]
target = 1.25
```
Output:
```text
2
```
Explanation: `1.00 + 0.25 = 1.25`, using two coins.
Constraints:
- `1 <= denominations.length <= 100`
- `0 < denomination <= 10,000`
- `0 <= target <= 10,000`
- All monetary values have at most two digits after the decimal point.
Requirements:
- Do not run dynamic programming directly on floating-point values.
- Convert decimal values to scaled integers, then solve the integer coin-change problem.
- Aim for `O(target * number_of_denominations)` time after scaling and `O(target)` space.
Quick Answer: This question evaluates proficiency in dynamic programming for coin-change problems and competency in numerical precision and safe handling of decimal monetary values in algorithmic implementations.
Given a list of coin denominations represented as decimal monetary values and a target amount represented as a decimal value, return the minimum number of coins needed to sum exactly to the target. You may use each denomination an unlimited number of times.
If the target cannot be formed exactly, return -1.
Because the values are decimals, you must avoid running dynamic programming directly on floating-point numbers. Instead, safely convert every monetary value to a scaled integer amount (such as cents) and then solve the standard minimum coin change problem.
Constraints
- 1 <= len(denominations) <= 100
- 0 < denomination <= 10000
- 0 <= target <= 10000
- All monetary values have at most two digits after the decimal point
- Do not perform dynamic programming directly on floating-point values
Examples
Input: ([0.25, 0.50, 1.00], 1.25)
Expected Output: 2
Explanation: The best choice is 1.00 + 0.25 = 1.25, which uses 2 coins.
Input: ([0.01, 0.03, 0.04], 0.06)
Expected Output: 2
Explanation: A greedy choice of 0.04 first would need 3 coins total, but 0.03 + 0.03 forms 0.06 with only 2 coins.
Input: ([0.30, 0.50], 0.40)
Expected Output: -1
Explanation: Neither 0.30 nor 0.50 can combine to make exactly 0.40.
Input: ([0.25, 0.50], 0.00)
Expected Output: 0
Explanation: Zero coins are needed to make a target of 0.00.
Input: ([0.10, 0.20, 0.30], 0.60)
Expected Output: 2
Explanation: The minimum is 0.30 + 0.30 = 0.60, so the answer is 2.
Hints
- Convert each value to an integer number of cents first. Using Decimal(str(x)) is safer than relying on raw float arithmetic.
- After scaling, this becomes the classic unbounded minimum coin change problem that can be solved with a 1D DP array.