Minimum Coins Dynamic Programming | Dataford Interview Questions

A Nissan Motor payment kiosk accepts a fixed set of coin denominations. Given the denominations and a target amount, return the minimum number of coins needed to produce that amount. Each denomination may be used any number of times. Return -1 if the amount cannot be formed.

Formal Specification

Implement coin_change(coins, amount), where coins is a list of positive integers and amount is a non-negative integer. Return an integer representing the smallest number of coins whose values sum to amount, or -1 when no valid combination exists.

Constraints

1 <= len(coins) <= 12
1 <= coins[i] <= 10^4
0 <= amount <= 10^4
Coin denominations may be used repeatedly.
Duplicate denominations may be present.

Function Signature

def coin_change(coins, amount):

Your question is Minimum Coins Dynamic Programming. 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

Constraints

1 <= len(coins) <= 12
1 <= coins[i] <= 10^4
0 <= amount <= 10^4
Coin denominations may be used repeatedly.
Duplicate denominations may be present.

Function Signature

def coin_change(coins, amount):

Your question is Minimum Coins Dynamic Programming. 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.