Katkat
Back

Minimum Bills and Coins to Make Change

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to determine the optimal combination of coins and bills to achieve a specific target amount, while managing limited inventory and precision issues.

Problem Statement

Given an amount of money target (as a float) and a dictionary inventory representing the available count for each denomination (e.g., {100: 2, 20: 5, 5: 10, 1: 5, 0.25: 4, 0.10: 10, 0.05: 20, 0.01: 50}), write a function to return the minimum number of items needed to reach exactly the target amount.

If it is impossible to form the exact amount with the given inventory, return -1. Assume denominations are standard currency values.

Function Signature

def min_change(target: float, inventory: dict[float, int]) -> int:

Examples

Example 1:

  • Input: target = 6.30, inventory = {5: 1, 1: 2, 0.25: 2, 0.05: 1}
  • Output: 5 (One 5-bill, one 1-bill, one 0.25-coin, one 0.05-coin is not enough, but five 1-bills and six 0.05-coins etc. - you must find the minimum count).

Example 2:

  • Input: target = 0.40, inventory = {0.25: 1, 0.05: 1}
  • Output: -1

Constraints

  • Use integer arithmetic by scaling the currency (e.g., multiply everything by 100) to avoid floating-point errors.
  • The greedy approach works here because standard denominations are "canonical," but you must account for the limited inventory constraint.

Considerations

  • How do you handle the inventory constraint when the largest available denomination isn't enough to reach the target optimally?

Hints

Hint 1

Convert all currency values to cents (integers) by multiplying by 100 to eliminate floating-point precision issues.

Hint 2

Sort the available denominations in descending order and try to use as many of the largest denomination as possible before moving to the next smaller one.

Hint 3

Because inventory is limited, this problem behaves more like a variation of the change-making problem where you must use a greedy approach coupled with a check against available counts.

Follow-up questions

  • How would your approach change if the denominations were not standard (e.g., {1, 3, 4}) where a greedy approach might fail to find the global optimum?
  • If we had an infinite supply of each coin, how would the time complexity change?
  • How would you modify the function to return the actual count of each denomination used rather than just the total number of items?