1
\$\begingroup\$

This is a Python solution for all general cases. Any suggestions at all would be appreciated; in my opinion it's already quite good! Here's a link to the problem.

from timeit import default_timer as timer

def count_coins(target, operands):
    ways_to_make = [1] # list of ways to make x at index x
    for o in range(0, len(operands)):
        for t in range(target + 1):
            # initialise undefined target
            if len(ways_to_make) <= t:
                ways_to_make.append(0)
            # add ways to make number recursively
            if t >= operands[o]:
                ways_to_make[t] += ways_to_make[t - operands[o]]

    return ways_to_make[target]

start = timer()
ans = count_coins(200, [1, 2, 5, 10, 20, 50, 100, 200])
elapsed_time = (timer() - start) * 1000 # s --> ms

print "Found %d in %r ms." % (ans, elapsed_time)
\$\endgroup\$
7
\$\begingroup\$

It will be faster if you pre-generate the ways_to_make array:

def count_coins(sum, coins):
    ways_to_make = [0 for _ in range(sum + 1)]
    ways_to_make[0] = 1
    for coin in coins:
        for t in range(sum + 1):
            if t >= coin:
                ways_to_make[t] += ways_to_make[t - coin]

    return ways_to_make[sum]

This doesn't waste memory because you would allocate those elements anyway, and it's a lot faster to create a larger list once than extending it in every loop iteration. Not to mention that this gets rid of an if statement.

I also changed the for o in range(len(coins)) loop to the more intuitive for coin in coins. In my measurements this gave an extra speed boost too.

Finally, I took the liberty to rename your function parameters to more meaningful names.

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

I will add a bit to janos's answer.

The inner loop

for t in range(sum + 1):
    if t >= coin:
        ways_to_make[t] += ways_to_make[t - coin]

can be written better as

for t in range(coin, sum + 1):
    ways_to_make[t] += ways_to_make[t - coin]

It becomes automatically clear that here t >= coin

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.