Thursday, April 09, 2015

ways, coins used for n cents

Count number of ways and coins used for n cents given set of coins.

coins = { 5, 10, 25 }
// without caching
count-ways(n, coins = [5, 10, 25]):
    if n <= 0:
        return 0
    return (n, coins)
count-ways(n, coins):
    if n == 0:
        return 1
    if n < 0:
        return 0
    ncount = 0
    for coin in coins:
        ncount += (n-coin, coins)
    return ncount
count-ways(10) =2
    (5)
        (0) =1
    (0) =1

count-ways(7) =0
    (2) =0
        (-3) =0

Bubble -1 up if count is 0 for n.
// cache[i] = int.min initially, cache[0] is for 1
count-coins(n, coins = [5, 10, 25], cache):
    if n == 0:
        return 0
    if n < 0:
        return -1
    if cache[n-1] >= -1:
        return cache[n-1]
    ncount = 0
    foreach coin in coins:
        count = count-coins(n-coin, coins, cache)
        if count != -1:
            ncount += 1 + count
    // bubble -1 up
    if ncount == 0:
        ncount = -1
    cache[n-1] = ncount
    return ncount
count-coins(10) =3
    (5) =1
        (0) =0
    (0) =0

count-coins(7) =-1
    (2) =-1
        (-3)=-1

[Hat tip to ctci]

No comments:

Post a Comment