Minimum Bills and Coins to Make Change
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are building the change-dispensing logic for a self-checkout cash register. Given a purchase change amount (in dollars, e.g. `6.35`), compute the **minimum total number of physical pieces** (bills plus coins) needed to make up that exact amount.
The available denominations are:
- **Bills:** `$20`, `$10`, `$5`, `$1`
- **Coins:** `$0.25`, `$0.10`, `$0.05`, `$0.01`
Return the total count of pieces and the breakdown — how many of each denomination is used.
### Constraints
- `0 <= amount`, and `amount` has at most two decimal places (it is a whole number of cents).
- `amount` fits comfortably in a 64-bit integer after conversion to cents.
### Input / Output
- **Input:** a non-negative amount in dollars (e.g. `6.35`).
- **Output:** the minimum number of pieces (an integer), plus the per-denomination counts used.
### Example
```
amount = 6.35
Output: 4
Breakdown: one $5 bill, one $1 bill, one $0.25 coin, one $0.10 coin.
```
(`$5 + $1 + $0.25 + $0.10 = $6.35`, using 4 pieces.)
---
### Follow-up 1 — Early exit
Once the remaining amount reaches `0`, there is no need to keep iterating. How would you modify your loop to stop as soon as change is fully made?
### Follow-up 2 — Limited inventory
The register's cash drawer holds a **finite stock** of each denomination, given as a count per denomination. How would you modify your solution to respect these inventory limits? If the available stock is insufficient to make exact change, return a sentinel value (e.g. `-1`) instead of an incorrect count. Discuss any trade-offs in your approach.
Quick Answer: This question tests a candidate's grasp of greedy algorithms applied to a classic coin-change problem with fixed denominations. It evaluates practical algorithm design skills, including integer arithmetic handling for floating-point currency values and optimization under real-world constraints like limited inventory.
Minimum Bills and Coins to Make Change
You are building the change-dispensing logic for a self-checkout cash register. Given a purchase change `amount` (in dollars, e.g. `6.35`), compute the **minimum total number of physical pieces** (bills plus coins) needed to make up that exact amount, and report the per-denomination breakdown.
The available denominations are:
- **Bills:** `$20`, `$10`, `$5`, `$1`
- **Coins:** `$0.25`, `$0.10`, `$0.05`, `$0.01`
With these canonical US-style denominations and unlimited stock, a **greedy** strategy (repeatedly take as many of the largest denomination that still fits) is provably optimal for minimizing the piece count.
### Output format
Return a list of 9 integers: `[total, c2000, c1000, c500, c100, c25, c10, c5, c1]` where `total` is the minimum number of pieces and the remaining 8 entries are the counts used for `$20, $10, $5, $1, $0.25, $0.10, $0.05, $0.01` respectively (denominations in cents-descending order).
### Example
```
amount = 6.35
Output: [4, 0, 0, 1, 1, 1, 1, 0, 0]
```
4 pieces total: one $5 bill, one $1 bill, one $0.25 coin, one $0.10 coin ($5 + $1 + $0.25 + $0.10 = $6.35).
### Follow-up — Early exit
Once the remaining amount reaches `0`, you can stop iterating the remaining denominations entirely. A `break` jumps to the first statement after the loop (not the next iteration), so the partial breakdown built so far is already complete.
Constraints
- amount >= 0 and has at most two decimal places (a whole number of cents).
- amount fits comfortably in a 64-bit integer after conversion to cents.
- Always convert dollars to integer cents first (round(amount * 100)) to avoid floating-point error.
Examples
Input: (6.35,)
Expected Output: [4, 0, 0, 1, 1, 1, 1, 0, 0]
Explanation: $5 + $1 + $0.25 + $0.10 = $6.35 using 4 pieces.
Input: (0,)
Expected Output: [0, 0, 0, 0, 0, 0, 0, 0, 0]
Explanation: Zero change requires zero pieces (edge case).
Input: (0.99,)
Expected Output: [9, 0, 0, 0, 0, 3, 2, 0, 4]
Explanation: 3 quarters + 2 dimes + 4 pennies = $0.99 in 9 pieces.
Input: (20,)
Expected Output: [1, 1, 0, 0, 0, 0, 0, 0, 0]
Explanation: A single $20 bill (boundary on the largest denomination).
Input: (47.18,)
Expected Output: [10, 2, 0, 1, 2, 0, 1, 1, 3]
Explanation: 2x$20 + $5 + 2x$1 + $0.10 + $0.05 + 3x$0.01 = $47.18 in 10 pieces.
Input: (0.01,)
Expected Output: [1, 0, 0, 0, 0, 0, 0, 0, 1]
Explanation: A single penny (smallest unit).
Input: (99.99,)
Expected Output: [19, 4, 1, 1, 4, 3, 2, 0, 4]
Explanation: Largest test amount; 4x$20 + $10 + $5 + 4x$1 + 3x$0.25 + 2x$0.10 + 4x$0.01 = $99.99 in 19 pieces.
Hints
- Convert dollars to integer cents immediately: cents = round(amount * 100). Never do greedy arithmetic on floats.
- Process denominations from largest to smallest; for each, take floor(cents / denom) of them and subtract.
- Greedy is optimal here because each denomination divides evenly into a combination of smaller ones for this canonical denomination set.
Minimum Bills and Coins with Limited Inventory
Extend the change-maker: the register's cash drawer now holds a **finite stock** of each denomination. Given the `amount` and an `inventory` array, return the **minimum total number of pieces** to make exact change without exceeding the available stock of any denomination. If exact change is impossible with the given stock, return `-1`.
`inventory` is a list of 8 non-negative integers giving the count available for each denomination in cents-descending order: `[$20, $10, $5, $1, $0.25, $0.10, $0.05, $0.01]`.
### Why greedy no longer works
With limited stock, greedily taking the largest denomination can both produce a non-minimal count and even fail to find a valid combination that exists. For example, `amount = $0.30` with inventory `{one $0.25, three $0.10, nothing else}`: greedy takes the quarter and then cannot make the remaining $0.05, returning failure — yet three dimes make exactly $0.30 in 3 pieces. This is a **bounded knapsack** problem; solve it with dynamic programming over the cents amount.
### Example
```
amount = 0.30, inventory = [0,0,0,0,1,3,0,0]
Output: 3 (three $0.10 coins)
```
### Trade-offs
The DP runs in O(cents x sum(inventory)) time and O(cents) space using a 0/1-knapsack pass per available unit, or O(cents x denominations) with a monotonic-deque bounded-knapsack optimization. Greedy is O(denominations) but incorrect under limited stock. For typical register amounts (cents in the low thousands) the DP is fast and exact.
Constraints
- amount >= 0 with at most two decimal places; convert to integer cents.
- inventory has exactly 8 non-negative integers for [$20,$10,$5,$1,$0.25,$0.10,$0.05,$0.01].
- Return -1 when no combination within the stock makes exact change.
- Greedy is incorrect under limited stock; a DP (bounded knapsack) is required for correctness.
Examples
Input: (6.35, [10, 10, 10, 10, 10, 10, 10, 10])
Expected Output: 4
Explanation: Ample stock matches the unlimited greedy answer: $5 + $1 + $0.25 + $0.10 = 4 pieces.
Input: (0, [0, 0, 0, 0, 0, 0, 0, 0])
Expected Output: 0
Explanation: Zero change needs zero pieces even with empty drawer.
Input: (0.30, [0, 0, 0, 0, 1, 3, 0, 0])
Expected Output: 3
Explanation: Greedy-fail case: taking the quarter strands $0.05; the DP instead uses three dimes for 3 pieces.
Input: (0.03, [0, 0, 0, 0, 5, 5, 5, 0])
Expected Output: -1
Explanation: No pennies in stock, so 3 cents is impossible to make exactly.
Input: (0.04, [0, 0, 0, 0, 0, 0, 0, 3])
Expected Output: -1
Explanation: Only 3 pennies available but 4 cents needed -> impossible.
Input: (0.03, [0, 0, 0, 0, 0, 0, 0, 3])
Expected Output: 3
Explanation: Exactly 3 pennies make $0.03 in 3 pieces (inventory boundary).
Input: (6.35, [10, 10, 10, 10, 0, 10, 10, 10])
Expected Output: 6
Explanation: No quarters: $5 + $1 + 3x$0.10 + $0.05 = 6 pieces.
Input: (0.50, [0, 0, 0, 0, 2, 0, 0, 0])
Expected Output: 2
Explanation: Two quarters make exactly $0.50 in 2 pieces.
Input: (0.40, [0, 0, 0, 0, 2, 0, 0, 0])
Expected Output: -1
Explanation: Only quarters available; no subset sums to $0.40 -> impossible.
Hints
- Work in integer cents. dp[t] = minimum pieces to make exactly t cents; dp[0] = 0, everything else infinity.
- For each denomination, allow it to be used at most inventory[i] times — a bounded knapsack. The simplest correct form runs a 0/1-knapsack reverse-iteration pass once per available unit.
- Cap the usable units of each denom at min(inventory[i], cents // denom) to avoid wasted work.
- If dp[cents] is still infinity at the end, exact change is impossible — return -1.