Project Euler Problem #20:

Problem #20 is quite surprisingly the first problem to feature the factorial. I’d explain it, but the question already does it for me. Here’s the question:

Project Euler Problem 20: Factorial digit sum
n! means n x (n-1) x . . . x 3 x 2 x 1

For example, 10! = 10 x 9 x . . . x 3 x 2 x 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!

My solution for this problem is pretty boring. Here it is:

Solution #1: Brute Force Approach

We simply calculate 100! and add up its digits by converting it to a string and adding the integer associated with each character. I’m not sure if this saves time, but I divided the running product by 10 whenever it was a multiple of 10 to make the value smaller without changing the sum of the digits. Here’s an implementation of this method in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #20
 '''

 import time

 def projectEulerProblemTwenty(n):
     total = 1
     for i in range(2,n+1):
         if(total%10==0):
             total/=10
         total*=i
     a = str(total)
     final = 0
     for l in a:
         final+=int(l)
     return final

 start = time.time()
 print projectEulerProblemTwenty(100)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints

 648
 --- 0.000115871429443 seconds ---

 for input of n=100
 '''

As shown above, Python is great even when dealing with massive numbers such as 100!. This problem is probably another good contender for simplest Project Euler problem looking back on it.

Thanks for reading. See you tomorrow!