#### Problem 34: Digit Factorials

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits. **Note**: as 1! = 1 and 2! = 2 are not sums they are not included.

#### The Catch

How to determine the upper bound of the search range.

How to efficiently calculate factorial.

How to efficiently manipulate the digits to find their sum.

#### The Light

Similar to the analysis in Problem 30:

The lowest 7-digit number is 1,000,000, the maximum sum of factorial of their digits is 9! * 7 = 2,540,160.

The lowest 8-digit number is 10,000,000, the maximum sum of factorial of their digits is only 9! * 8 = 2,903,040. This indicates no 8-digit number can be written as the sum of factorial of their digit. Upper bound is **2,540,160**.

In this problem, only 0! to 9! are needed, so calculate their results and store in an array to avoid repeated calculations.

Similar to the technique in Problem 37, perform a modulus of 10 on a number to get its last digit. Take advantage of this to calculate the digit sum.

#### The Code

public class Problem34 { public static void main(String[] args) { int sum = 0; int[] fact = fact(); for(int i = 10; i <= 2540160; i++) { int tmp = i; int tmpSum = 0; while(tmp > 0) { tmpSum += fact[tmp % 10]; tmp /= 10; } if(tmpSum == i) sum += i; } System.out.println(sum); } public static int[] fact() { int[] fact = new int[10]; fact[0] = 1; for(int i = 1; i < fact.length; i++) { int tmp = i; int result = 1; while(tmp > 1) { result *= (tmp--); } fact[i] = result; } return fact; } }