# Project Euler

### A Taste of Number Theory

#### 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!

#### The Catch

How to efficiently calculate factorial.
How to store an extremely large number.

#### The Light

Factorial calculation is much more efficient using the iterative approach as opposed to the recursive one. To find x!, keep multiplying x by x - 1 every time until x reaches 1. That way, the factorial-finding loop is nothing but a sequence of simple multiplication, which is what computer is very good at.

Use Java's BigInteger class. Then parse the result into an array of digit-character to calculate their sum.

#### The Code

```import java.math.BigInteger;

public class Problem20
{
public static void main(String[] args)
{
BigInteger n = new BigInteger("100");
BigInteger result = BigInteger.ONE;

while(n.compareTo(BigInteger.ONE) == 1)
{
result =  result.multiply(n.subtract(BigInteger.ONE));
n = n.subtract(BigInteger.ONE);
}

System.out.println("Result: " + result);

String s = result.toString();
char[] array = new char[s.length()];
array = s.toCharArray();

int sum = 0;
for(int i = 0; i < array.length; i++)
{
sum += Character.getNumericValue(array[i]);
}

System.out.println(sum);
}
}
```