Fewest Bills and Coins | Dataford Interview Questions

In an Inspire11 payment workflow, determine how to provide exact change using the fewest available bills and coins. Given an amount in cents and a list of available denominations, return how many of each denomination to use.

Implement make_change(amount, denominations). The result must be a list whose length matches denominations; element i is the number of coins or bills with value denominations[i]. Return None when the amount cannot be formed. Any representation using the minimum total number of items is valid.

Formal Specification

amount: a nonnegative integer representing cents.
denominations: a list of distinct positive integers representing cents.
Return a list of nonnegative integer counts, or None if no exact representation exists.
Each denomination may be used unlimited times.

Constraints

0 <= amount <= 100,000
1 <= len(denominations) <= 50
1 <= denominations[i] <= amount when amount > 0
Denominations are distinct positive integers
Each denomination can be used unlimited times

Function Signature

def make_change(amount, denominations):

Your question is Fewest Bills and Coins. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Formal Specification

amount: a nonnegative integer representing cents.
denominations: a list of distinct positive integers representing cents.
Return a list of nonnegative integer counts, or None if no exact representation exists.
Each denomination may be used unlimited times.

Constraints

0 <= amount <= 100,000
1 <= len(denominations) <= 50
1 <= denominations[i] <= amount when amount > 0
Denominations are distinct positive integers
Each denomination can be used unlimited times

Function Signature

def make_change(amount, denominations):

Your question is Fewest Bills and Coins. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.