Katkat
Back

Solve Decimal Coin Change

AirbnbMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

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 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:

denominations = [0.25, 0.50, 1.00]
target = 1.25

Output:

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.