Make Change with Fewest Notes

Medium ⏱ 12 min 55% acceptance ★★★★☆ 4.4
Indian denominations: 2000, 500, 200, 100, 50, 20, 10, 5, 2, 1. Write change(amount) returning a dict denomination → count using the greedy algorithm (largest first), omitting zero-count notes. (Greedy is optimal for this canonical system — worth stating.)

Examples

Example 1
Input
change(3876)
Output
{2000: 1, 500: 3, 200: 1, 100: 1, 50: 1, 20: 1, 5: 1, 1: 1}
Explanation

Largest notes first minimizes the count.

Constraints

  • Omit denominations with count 0.
  • divmod your way down.

Topics

Business Logicgreedy change

Companies

NCRPine LabsBharatPe

Hints

Hint 1

Loop the denomination list in order.

Hint 2

count, amount = divmod(amount, note).

← Score Sales Leads Auto-Moderate Product Reviews →
Loading the Python runtime… Run executes your code and shows printed output; Submit checks your function against this problem's examples.