Project Euler Problem 20 Solution

Project Euler & HackerRank Problem 20 Solution

Factorial digit sum
by {BetaProjects} | MAY 18, 2009 | Project Euler & HackerRank

Project Euler Problem 20 Statement

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

Find the digit sum in the number 100!

Solution

Python natively supports arbitrary-precision integers and arithmetic with as many digits as necessary to perform a calculation. For example, it takes 158 digits to represent 100! and Python handles it easily.

To solve this problem we calculate 100! using the factorial function from the math library and convert the result to a string so we can iterate over each character-digit. This conversion is required because integers are not iterable, but strings are.

sum(map(int,str(factorial(100))))

Then, using the map function we convert every character-digit back to an integer. This allows us to break the individual digits apart and add them up for a digit sum using the sum function.

sum(map(int, str(factorial(100))))

HackerRank version

HackerRank’s Project Euler 20 increases the factorial from 100 to 0 ≤ N ≤ 1,000 and runs 100 test cases. This solution was fast enough to handle these parameters without change.

Python Source Code

Last Word

Embrace the power of arbitrary-precision integers and ignore the call to solve it in some primitive way.

See also, Project Euler 16: Digit sum for a large power of 2