3
\$\begingroup\$

n! means n × (n − 1) × ... × 3 × 2 × 1

For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800, and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27. Find the sum of the digits in the number 100!

def fact(n):
    """returns factorial of n."""
    if n <= 1:
        return 1
    return n * fact(n - 1)


def count_digits(n):
    """Assumes n > 1.
    returns sum of digits of n's factorial."""
    factorial = fact(n)
    total = 0
    for digit in str(factorial):
        total += int(digit)
    return total


if __name__ == '__main__':
    print(count_digits(100))
\$\endgroup\$
2
\$\begingroup\$

The standardlibrary module math already contains a factorial function. On my machine it is about 20 times faster than your function using n = 100. It also does not suffer from stack size limitations as yours does (try computing fact(3000)).

Alternatively you could learn about memoizing, which will help you in many Project Euler problems. Here it would be useful if you had to evaluate the factorial of many numbers (and even better if the numbers are increasing).

from functools import wraps

def memoize(func):
    cache = func.__cache = {}

    @wraps(func)
    def wrapper(*args, **kwargs):
        key = args, frozenset(kwargs.items())
        if key in cache:
            ret = cache[key]
        else:
            ret = cache[key] = func(*args, **kwargs)
        return ret
    return wrapper


@memoize
def fact(n):
    ...

Note that this decorator only works if your arguments are hashable (so no lists for example).


Since getting the sum of the digits of a number is something you will regularly need for Project Euler problems, you should make it a function on its own, which you put in a utils module, to be reused later:

def digit_sum(n):
    """Return the sum of the digits of `n`"""
    return sum(map(int, str(n)))

This will also be faster than your manual for loop or a list comprehension. Not by much, but it is measurable for very large numbers:

def digit_sum_list_comprehension(n):
    return sum(int(x) for x in str(n))

def digit_sum_for(n):
    total = 0
    for digit in str(n):
        total += int(digit)
    return total

enter image description here

\$\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.