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!

Algorithm to Compute Factorial Digit Sum

Since the factorial could be very large, we need to use an array (or hashmap) to store the digits of the answer. However, in some programming language, large values can be stored e.g. BigInteger in Java or Python.

Similar to Digit factorials: Find the Sum of All the Curious Numbers, we will compute the factorial and store the value in a dictionary.

Then the digits (values of the dictionary) are iterated and sum is obtained via the Array.reduce() function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

let arr = {
    0: 1
};
 
for (let i = 2; i <= 100; ++i) {
    // multiply by value i
    Object.keys(arr).map(x => {
        arr[x] *= i;
    });
    let c = Math.floor(arr[0] / 10);
    let j = 1;
    arr[0] %= 10;
    // higest position of the value
    const maxKey = Math.max(...Object.keys(arr));
    while ((c > 0) || (j <= maxKey)) {
        if (typeof arr[j] === 'undefined') {
            arr[j] = c;
        } else {
            arr[j] = arr[j] + c;
        }
        // carry over
        c = Math.floor(arr[j] / 10);
        arr[j] %= 10;
        j ++;
    }
}
 
// sum up all the digits of the answer
console.log(Object.values(arr).reduce((a, b) => a + b));

let arr = {
    0: 1
};

for (let i = 2; i <= 100; ++i) {
    // multiply by value i
    Object.keys(arr).map(x => {
        arr[x] *= i;
    });
    let c = Math.floor(arr[0] / 10);
    let j = 1;
    arr[0] %= 10;
    // higest position of the value
    const maxKey = Math.max(...Object.keys(arr));
    while ((c > 0) || (j <= maxKey)) {
        if (typeof arr[j] === 'undefined') {
            arr[j] = c;
        } else {
            arr[j] = arr[j] + c;
        }
        // carry over
        c = Math.floor(arr[j] / 10);
        arr[j] %= 10;
        j ++;
    }
}

// sum up all the digits of the answer
console.log(Object.values(arr).reduce((a, b) => a + b));

–EOF (The Ultimate Computing & Technology Blog) —