Project Euler Solution 20: Factorial digit sum

Here we have Project Euler Problem 20: Factorial digit sum, which is about the sum of the digits in 100!. It can be solved in a single line in Python.

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!

In most programming languages the problem is that 100! exceeds the representable integers. In Python we don't have to worry about that. We can just compute that number, convert it into a string, loop over the digits, convert them back to integers, and sum them up.

This can be done in a single line of Python:

def solution_functional() -> int:
    return sum(map(int, str(functools.reduce(lambda a, b: a * b, range(1, 101)))))

I think that the algorithm here isn't that interesting in itself, but the functional style of programming is interesting to write about. Let us unpack it a bit. We have the range(1, 101), which can be throught of as the list [1, 2, …, 100]. But more accurate is to think of it as a generator that will generate these numbers as we go through them. The numbers never exist in memory all the time, they are generated as needed. This means that I can write range(10**100) without that filling my computer memory. In Python 2 it would actually generate the list, but in Python 3 it is just a generator.

Next we have the functools.reduce. This uses a binary reduction to reduce a sequence of elements. That might sound fancy, but it just means that we take the number 1 to 100 and pairwise apply the function to it to yield a new value. And then we take that result value and apply that operation to another element in the sequence. We do that until only one value is left. The function I supply is a lambda, an anonymous function. It takes a and b and returns the product. This means that we reduce the number 1 to 100 by multiplying them together until only one value is left. And that value then is 100!.

Then I use str to convert this integer number into a string representation with base 10. I want to convert each digit back into an integer. I use the map function which takes a function, here int, and maps it to a sequence. This sequence is the string. Python strings are iterable and iterate over the individual characters, which fits perfectly. The result of the map operation is a sequence of integers. And then I feed that into the sum function to sum over all these numbers. And sum is also a reduction, with with the plus operation.

We can write a second version in a procedural style. That then looks like this:

def solution_procedural() -> int:
    factorial = 1
    for factor in range(1, 101):
        factorial *= factor

    digit_sum = 0
    for digit_char in str(factorial):
        digit_sum += int(digit_char)

    return digit_sum

The functional style is very different. And it is very difficult when one is not used to it. After reading a book on Haskell, I have an idea of the functional style and quite like it. Python 3 has many functional elements in it, most importantly the generator/iterator/coroutine concept. I encourage you to give it a try and unlock a completely new way of thinking of problems.