You are given a list of distinct positive coin denominations and a target amount. You have an unlimited supply of each coin. Return the minimum number of coins whose values add up to exactly amount, or -1 if no combination of the coins can reach it. def fewest_coins(coins: List[int], amount: int) -> int: pass Input coins a list of distinct positive integers (the denominations available). amount a non-negative integer target. Output An int, the fewest coins summing to amount, or -1 if it cannot be made. Examples fewest_coins([1, 2, 5], 11) returns 3 (5 + 5 + 1). fewest_coins([2], 3) returns -1 (an odd target is unreachable with only 2s). fewest_coins([1], 0) returns 0 (zero coins make a zero amount).

Bottom-up DP over amounts: dp[a] is the minimum coins to make a, with dp[0] = 0 and every other cell built from 1 + dp[a - c] across the coins. Use a sentinel (anything bigger than amount) for unreachable amounts. This is O(amount * len(coins)) time and O(amount) space. from typing import List def fewest_coins(coins: List[int], amount: int) -> int: # A real solution can use at most `amount` coins (smallest coin is >= 1), # so amount + 1 is a safe "infinity" sentinel for unreachable amounts. INF = amount + 1 dp = [0] + [INF] * amount # dp[a] = fewest coins to make a; dp[0] = 0. for a in range(1, amount + 1): for c in coins: if c

Complete Training For Your Trading Interview

Interview Questions Programming Fewest Coins

Unlock

Sorry, you don't have access to this interview question. Sign up to practice with our wide range of interview questions or use the filters to find free examples!

Python scratchpad

# Run Python right here in your browser
def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return [seen[target - n], i]
        seen[n] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

Run Python in your browser

Write and execute code — numpy, pandas & scikit-learn included — right on the question page.

My Notes

Notes are saved in this browser only. Sign up to keep them in your account.

The Interview Guide for Quants and Traders

Fewest Coins

What do you think of this page?