Problem #20 easy

Factorial digit sum

\(n!\) means \(n \times (n - 1) \times \dots \times 3 \times 2 \times 1\).

For example, \(10! = 10 \times 9 \times \dots \times 3 \times 2 \times 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!\).

Additional Notes

This problem involves calculating 100! and summing its digits. Since 100! has over 150 digits, the solution implements manual digit-by-digit multiplication with carry handling in an array. This approach avoids the need for arbitrary-precision arithmetic libraries while efficiently computing the factorial.

cpp

Implementations

O(n²) time complexity for factorial calculation

View Raw

#include <iostream>

static const int big_size = 500;

int factorial_digit_sum(int fme)
{
  int digits[big_size] = {0};
  digits[0] = 1;

  int high_water = 2;

  for (size_t factor = 2; factor <= fme; factor++) {
    int carry = 0;
    for (size_t j = 0; j < high_water; j++) {
      int x = digits[j] * factor + carry;
      digits[j] = x % 10;
      carry = x / 10;
    }
    while (carry > 0) {
      digits[high_water] = carry % 10;
      carry /= 10;
      high_water++;
    }
  }

  int ret = 0;
  for (size_t i = 0; i < high_water; i++) {
    ret += digits[i];
  }
  return ret;
}

int main(int argc, char const *argv[])
{
  std::cout << "Answer: " << factorial_digit_sum(100) << std::endl;
}

All Solutions