[C/C++] Project Euler #34 - Digit Factorials

This problem is about finding numbers that are equal to the sum of the factorials of their digits.

For example, the number 145 is such a number because

\[1! + 4! + 5! = 1 + 24 + 120 = 145\]

This problem asks you to find the sum of all such numbers.

If you've been working on Project Euler problems up to this point, you probably have some experience with extracting digits from a decimal number.

In my case, I pre-calculated and stored the factorial values for each digit. Since 9! = 362880, I figured the numbers we're looking for would be roughly 6 digits long. That's why I set the number range accordingly.

 

Digit Factorial Calculation Visualization

 

//------------------------------------------------
//    Project Euler #34 - Digit Factorials
//        - by Aubrey Choi
//        - created at 2015-03-20
//------------------------------------------------
#include <stdio.h>

int main()
{
    int facts[10] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 36280 };

    int sum = 0;
    for( int i = 10 ; i < facts[9]*6 ; i++ )
    {
        int ss = 0;
        for( int k = i ; k ; ss += facts[k%10], k /= 10 ) ;
        if( ss == i ) sum += i;
    }
    printf("ans = %d\n", sum);
}

 

This C code solves Project Euler Problem 34, which involves finding numbers that equal the sum of the factorials of their digits. Here's a breakdown:

1. Header:

#include <stdio.h>

This line includes the standard input/output library, providing functions like `printf` for printing output to the console.

2. Factorial Lookup Table:

int facts[10] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };

This line creates an array named `facts` to store the factorial values of digits 0 through 9. This acts as a lookup table for quick access to factorials later in the code.

3. Main Function:

int main()
{
  // ... code ...
}

This is the main function where the program execution begins.

4. Initialization:

  int sum = 0;

This line initializes a variable `sum` to 0. This variable will store the sum of all the numbers that meet the problem's criteria.

5. Looping through Potential Numbers:

  for( int i = 10 ; i < facts[9]*6 ; i++ )
  {
    // ... code ...
  }

This `for` loop iterates through numbers from 10 up to `facts[9] * 6`. This upper limit is chosen because `facts[9]` (9!) is 362880, and it's unlikely that any number with more than 6 digits would satisfy the condition.

**6. Calculating the Sum of Digit Factorials:**

    int ss = 0;
    for( int k = i ; k ; ss += facts[k%10], k /= 10 ) ;

This nested `for` loop calculates the sum of the factorials of the digits of the current number `i`. 

  * `int ss = 0;`: Initializes a variable `ss` to store the sum of factorials.
  * `for( int k = i ; k ; ss += facts[k%10], k /= 10 ) ;`: This loop iterates through the digits of the number `i`.
      * `k = i`:  Assigns the current number `i` to `k`.
      * `k`: The loop continues as long as `k` is not zero.
      * `ss += facts[k%10]`:  Calculates the remainder when `k` is divided by 10 (`k % 10`) to get the last digit, then adds the factorial of that digit (obtained from the `facts` array) to `ss`.
      * `k /= 10`: Divides `k` by 10 to remove the last digit.

7. Checking for Equality:

   if( ss == i ) sum += i;

This line checks if the sum of the factorials of the digits (`ss`) is equal to the original number (`i`). If they are equal, the number `i` is added to the `sum`.

8. Printing the Result:

  printf("ans = %d\n", sum);

This line prints the final result (the `sum` of all numbers meeting the condition) to the console.

In summary, this program efficiently calculates the factorials of digits, iterates through potential candidates, and checks if they satisfy the given condition to find the solution to Project Euler Problem 34.