Problem 20 : Factorial Digit Sum

Factorial digit sum

Problem 20

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!

                                                                                                       (https://projecteuler.net/problem=20)

This one looks like a factorial problem, and it is, but more importantly, it is BigInteger again!

Factorial is really fun mathematical operator, as it will make a growth sharper than exponential function after a certain point.

So if you graph the function into a calculator, you will see that:

where red graph is y = e^x exponential graph,
and purple graph is y = x! factorial graph.

If we zoom in closer for 0 < x:

They meet each other at (5.29, 198.406), and after that point, factorial has much greater growth rate.

So, that being said, we definitely need BigInteger to get the value.


Starting with 1, up to 100, we use for-loop to multiply BigInteger values to get factorial 100!:

int ans = 0;
BigInteger num = BigInteger.ONE;
for (int i=1; i <= 100; i++) num = num.multiply(BigInteger.valueOf(i));

Just to let you know, there are default constants of BigInteger.ONE, BigInteger.ZERO, and BigInteger.TEN for convenience; there is multiply() function that you can use for multiplication; and you initialize the value using valueOf() function.

After that, we use the great advantage of Java BigInteger: the fact that it uses String to store the info.

So I will convert the String into char array, and use the char values to get each digit and their sum:

char[] arr = num.toString().toCharArray();
for (char c : arr) ans += c - '0';

System.out.println(ans);

And we will have the answer.

Answer is 648
Execution time is 2.634032 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem020.java

Graph Calculated from: https://www.desmos.com/calculator