Problem
https:projecteuler.net/problem=20
\(n!\) means: \(n × (n − 1) × ... × 3 × 2 × 1\)
For example,
\[10! = 10 × 9 × ... × 3 × 2 × 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!
Notes
We just avoid avoided needing a big integer class for the second time during these problems. The next time I need one, I will refactor the code below to something more generic.
Answer: 648
Solution
#include <iostream>
static const int big_size = 500;
int factorial_digit_sum(int fme)
{
int digits[big_size] = {0};
digits[0] =1;
int sum = 0;
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;
carry = 0;
sum = x;
if( x > 9){
sum = x % 10;
carry = x / 10;
if( j == high_water ){
high_water+=2;
}
}
digits[j]=sum;
}
}
int ret = 0;
for (size_t i = 0; i < high_water; i++) {
ret += digits[i];
}
return ret;
}
#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[])
{
std::cout << "Answer: " << factorial_digit_sum(100) << std::endl;
}
#endif // #if ! defined UNITTEST_MODE