Move History

Fork Selected
  • Description

    Given an array of positive integers representing coin denominations and a single non-negative integer n. representing a target amount of money, write a function that returns the smallest number of coins needed to make change for (to sum up to) that target amount using the given coin denominations.

    Example:

    sample Input n = 7 denoms = [1,5,10]

    output = 3//2x1+1x5

    time = O(nd),space = O(n). where n is target amount and d is number of coin denominations

    Note: you have access to an unlimited amount of coins.In other words,if denominations are [1,5,10],you have access to unlimited amount of 1s,5s and 10s

    If it's impossible to make change for target amount return -1

     Code 
    def minNumberOfCoinsForChange(n, denoms):
	numOfCoins = [float('inf') for amount in range(n+1)]  
	numOfCoins[0] = 0 
	for denom in denoms:
		for amount in range(len(numOfCoins)):
			if denom <= amount:
				numOfCoins[amount] = min(numOfCoins[amount],1+numOfCoins[amount - denom])
	return numOfCoins[n] if numOfCoins[n] != float('inf') else -1
     Test Cases 
    import codewars_test as test
# TODO Write tests
import solution # or from solution import example

# test.assert_equals(actual, expected, [optional] message)
@test.describe("Example")
def test_group():
    @test.it("test case")
    def test_case():
        test.assert_equals(minNumberOfCoinsForChange(7,[1,5,10]),3)
        test.assert_equals(minNumberOfCoinsForChange(7,[1,10,5]),3)
        test.assert_equals(minNumberOfCoinsForChange(7,[5,1,10]),3)
        test.assert_equals(minNumberOfCoinsForChange(0,[1,2,3]),0)
        test.assert_equals(minNumberOfCoinsForChange(3,[2,1]),2)
        test.assert_equals(minNumberOfCoinsForChange(4,[1,5,10]),4)
        test.assert_equals(minNumberOfCoinsForChange(10,[1,5,10]),1)
        test.assert_equals(minNumberOfCoinsForChange(24,[1,5,10]),6)
        test.assert_equals(minNumberOfCoinsForChange(9,[3,5]),3)
        test.assert_equals(minNumberOfCoinsForChange(10,[1,3,4]),3)
        test.it("good testcases")
        test.assert_equals(minNumberOfCoinsForChange(135,[39, 45, 130, 40, 4, 1, 60, 75]),2)
        test.assert_equals(minNumberOfCoinsForChange(135, [39, 45, 130, 40, 4, 1]),3)
    View Run Output