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!

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);
  }
}