ways to make change

[Albert Chan]

(03-02-2019 06:58 PM)Albert Chan Wrote:  PNDH ways = Σ( ((1+d) - 5k) * ((1+n-d) - 5k), k=0 to h )

Extending with all 5 coins (penny, nickel, dime, quarter, half-dollar) is now easy.
Just add quarters to PNDH ways, replacing half-dollar with quarters, 1 at a time.
Let this 5 coins helper function be f5:

f5 ways = Σ( (1+k) * ((1+d) - 5k) * ((1+n-d) - 5k), k=0 to h )

After simplication, this is final result:

Code:

def f5(x):
    n, d, h = x//5, x//10, x//50
    return ((75*h-20*n-15)*h + 6*(1+d)*(1+n-d)) * (h+1)*(h+2) // 12

def PNDQH(x): return f5(x) + f5(x-25)

>>> PNDQH(100) # ways to add to 1 dollar, with pennies, nickels, dimes, quarter, half-dollar
292

>>> PNDQH(100000) # how about 1000 dollars ?
66793412685001L