Digit Sum of a Large Factorial
National Olympiad — Regional round (2018 season)
Submission name: sdnf.cpp
Problem summary
Compute the decimal digit sum of n!, including factorials with thousands of digits.
Input
One integer n.
Output
The sum of the factorial’s digits.
Constraints
1 ≤ n ≤10000.
Worked example
Input and output for the worked example discussed below.
Input
65
Output
351
Solution analysis
- Store the exact factorial in little-endian base10^9 limbs. Each limb holds nine decimal digits, reducing work compared with one array element per digit.
- Start with1 and multiply by each integer2…n. For every limb compute limb×multiplier+carry, retain the remainder modulo10^9, and propagate the quotient. The temporary product fits64 bits for the given bounds.
- Sum ordinary decimal digits inside all final limbs. Conceptual leading zeros in an internal limb add nothing to this sum. For7!=5040 the result is9; the displayed65! example gives351.
Why it works
After multiplying by i the limb vector represents exactly i! by ordinary base arithmetic with carries. The limbs partition the final decimal digits into blocks, so summing their digit sums is exact.
Complexity: O(nD) time as a bound, for D digits in n!, and O(D) space. Every multiplication scans at most the final limb count.
Watch out. Floating-point factorials cannot recover exact digits. Use64-bit multiplication temporaries and retain all carry limbs.
Commented C++17 solution
An independently written complete program with standard headers.
#include<cstdint>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
cin>>n;
const uint64_t base=1000000000;
vector<uint32_t>limbs(1,1);
for(int multiplier=2;multiplier<=n;multiplier++){
uint64_t carry=0;
for(uint32_t&limb:limbs){
// Exact base-10^9 multiplication with a safe wide temporary.
uint64_t value=uint64_t(limb)*multiplier+carry;
limb=value%base;
carry=value/base;
}
while(carry>0){
limbs.push_back(carry%base);
carry/=base;
}
}
int answer=0;
for(uint32_t limb:limbs){
while(limb>0){
answer+=limb%10;
limb/=10;
}
}
cout<<answer<<'\n';
}